422. Possible Stack Order
Crates arrive at a loading dock one at a time in the order given by pushed, and each crate is placed on top of a single pile. At any moment the crate on top of the pile may be taken away. Crates are removed whenever you like, as long as only the top crate is ever taken, and you may interleave arrivals and removals freely.
You are given the arrival order pushed and a proposed removal order popped. Both contain the same distinct values. Return true if some sequence of arrivals and removals produces exactly the order popped, otherwise return false.
Example 1
- Input:
- pushed = [4,8,15,16,23], popped = [15,16,8,23,4]
- Output:
- true
- Explanation:
Place 4, 8, 15, remove 15; place 16, remove 16, remove 8; place 23, remove 23, remove 4. The order matches.
Example 2
- Input:
- pushed = [4,8,15,16,23], popped = [15,4,8,16,23]
- Output:
- false
- Explanation:
After 15 is removed the pile holds 4 and 8 with 8 on top, so 4 cannot leave before 8. No sequence of moves works.
Constraints
1 ≤ pushed.length ≤ 100000popped.length == pushed.length
All values are distinct, 1 ≤ pushed[i] ≤ 106, and popped is a permutation of pushed.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)