Use Side Lane
MediumP3Coding
order is a permutation of 1..N: the order in which N trucks arrive on a road. The trucks must leave in the order 1, 2, ..., N. Next to the road is a side lane that works like a stack: a truck can be parked at its end and only the truck at the entrance end can leave it, going to the output. Each arriving truck either goes straight to the output or is parked in the side lane.
Return true if it is possible to produce 1, 2, ..., N this way, otherwise false.
Example 1
- Input
- order = [5,1,2,4,3]
- Output
- true
- Why
- Park 5, send 1 and 2 straight out, park 4, send 3 out, then 4 and 5 leave from the lane.
Example 2
- Input
- order = [3,1,2]
- Output
- true
Example 3
- Input
- order = [2,3,1]
- Output
- false
- Why
- 1 is stuck behind nothing, but 2 is parked under 3 and cannot leave before 3.
Constraints
- 1 <= order.length <= 10^5
- order is a permutation of 1..order.length
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 12. ⌘Enter runs, ⌘⇧Enter submits.