Delivery Route Optimization with Retrace
Bigbasket delivery executives follow dynamic routes to fulfill orders. Due to various real-world factors like traffic, customer availability, or last-minute order changes, drivers often need to modify their planned routes. This problem simulates a simplified route management system that allows adding new stops, marking stops as delivered, and crucially, retracing previous actions. This functionality is essential for drivers to adapt quickly and maintain an efficient delivery flow.
You are tasked with implementing a function that processes a sequence of route management operations and returns the final state of the delivery route.
Your function should handle the following operations:
ADD <locationId>: Adds a new stop identified by locationId to the end of the current route. locationId will be a string.DELIVER: Marks the last stop in the current route as delivered. If the route is empty, this operation has no effect.RETRACE <k>: Undoes the last k successful ADD or DELIVER operations.
ADD <locationId> operation is undone, locationId is removed from the route.DELIVER operation is undone, the locationId that was previously delivered is added back to the route.k is greater than the number of available operations to undo, retrace all available operations.The final route should be returned as an array of locationId strings, ordered from the first stop to the last.
Input:
operations: An array of strings, where each string represents a single operation.
* ADD <locationId>: e.g., "ADD Bengaluru"
* DELIVER: e.g., "DELIVER"
* RETRACE <k>: e.g., "RETRACE 2" (where k is an integer string)
Output:
An array of strings (string[]) representing the locationIds in the final route, ordered from start to end.
locationId strings will consist of alphanumeric characters and spaces.k in RETRACE <k> will always be a positive integer.Examples
Example 1
Input:
operations = ["ADD A", "ADD B", "DELIVER", "ADD C"]
Output:
["A","C"]
Note:
ADD A: Route = [A]. History = [ADD A]ADD B: Route = [A, B]. History = [ADD A, ADD B]DELIVER: Route = [A]. History = [ADD A, ADD B, DELIVER B] (B was delivered)ADD C: Route = [A, C]. History = [ADD A, ADD B, DELIVER B, ADD C]
Final route: [A, C]Example 2
Input:
operations = ["ADD P", "ADD Q", "DELIVER", "ADD R", "RETRACE 2", "ADD S"]
Output:
["P","Q","S"]
Note:
ADD P: Route = [P]. History = [ADD P]ADD Q: Route = [P, Q]. History = [ADD P, ADD Q]DELIVER: Route = [P]. History = [ADD P, ADD Q, DELIVER Q]ADD R: Route = [P, R]. History = [ADD P, ADD Q, DELIVER Q, ADD R]RETRACE 2:
ADD R from history: Route becomes [P] (R removed).DELIVER Q from history: Route becomes [P, Q] (Q added back).
History is now [ADD P, ADD Q]ADD S: Route = [P, Q, S]. History = [ADD P, ADD Q, ADD S]
Final route: [P, Q, S]Example 3
Input:
operations = ["ADD X", "DELIVER", "DELIVER", "RETRACE 5", "ADD Y"]
Output:
["Y"]
Note:
ADD X: Route = [X]. History = [ADD X]DELIVER: Route = []. History = [ADD X, DELIVER X]DELIVER: Route = []. History unchanged (route was empty, no effect).RETRACE 5:
DELIVER X from history: Route becomes [X] (X added back).ADD X from history: Route becomes [] (X removed).
History is now []. k=5 was reduced to 2 as only 2 operations were available.ADD Y: Route = [Y]. History = [ADD Y]
Final route: [Y]Constraints
operations array length: 0 <= operations.length <= 10^5locationId string length: 1 <= locationId.length <= 20k in RETRACE <k>: 1 <= k <= 10^5ADD operations will not exceed 10^5.DELIVER and RETRACE.Loading editor...