Train cars arrive one at a time in the order given by arrival and are pushed into a dead-end siding, which works as a stack: only the most recently pushed car can leave. Cars can be moved out of the siding at any moment, in any interleaving with arrivals.
Return True if the cars can leave the siding in exactly the order departure, otherwise False. Both lists contain the same distinct values.
Examples
Input: arrival = [1, 2, 3, 4, 5], departure = [4, 5, 3, 2, 1]
Output: True
Explanation: push 1, 2, 3, 4; pop 4; push 5; pop 5; pop 3, 2, 1.
Input: arrival = [1, 2, 3, 4, 5], departure = [4, 3, 5, 1, 2]
Output: False
Explanation: 1 was pushed before 2, so 2 must leave before 1.
Constraints
0 <= len(arrival) == len(departure) <= 10**5- Target:
O(n)time
Goals
- Simulate a stack greedily against a target output order
- Recognise that popping whenever possible is never wrong