We have a system with these properties:
- System does a set of push and pop operations on a stack of integers.
- A pop operation is never done on empty stack.
- Each push operation increments an iteration variableI(integer) and pushes it into the stack.
- The system stops push operations once the iteration variable reaches N (a variable in the question).
- The iteration variable starts from 0.
- The system stops pop operations, once stack is empty.
- After each pop, the system writes out the popped element.
Given a list of integers, write a function that returns true, if for some N, that list can be outputted by a run of this system.
Example 1:
Input: [0, 3, 2, 1]
Output: true
Explanation: A set of valid operation with N = 3 is:
push (will push 0 and increment iteration to 1, stack is [0])
pop (will print 0, stack is [])
push (will push 1 and increment iteration to 2, stack is [1])
push (will push 2 and increment iteration to 3, stack is [2, 1])
push (will push 3 and increment iteration to 4, stack is [3, 2, 1])
pop (will print 3, stack is [2, 1])
pop (will print 2, stack is [1])
pop (will print 1, stack is [])Example 2:
Input: [0, 3, 1, 2]
Output: false
Explanation: To print `0`and `3`, steps 1 to 5 from the previous example will needed. After that there is no way to
print 1 without printing 2 since print happens on pop and 1 is after 2 in the stack.Comments (14)