Intermediate Level
Implement the validateStackPushPopSequence method that checks whether a pop sequence is valid for the given push sequence.
The input contains two integer arrays, pushed and popped, along with their length size. The pushed array shows the order in which values are pushed into a stack.
Your task is to check whether the popped array can be a valid pop order for that stack. A value can be popped only if it is currently on the top of the stack.
Example 1
Input
pushed (int[]) =
[1,2,3]popped (int[]) =
[2,3,1]size (int) =
3Returns (boolean)
trueExample 2
Input
pushed (int[]) =
[1,2,3,4,5]popped (int[]) =
[4,5,3,2,1]size (int) =
5Returns (boolean)
trueExample 3
Input
pushed (int[]) =
[1,2,3,4,5]popped (int[]) =
[4,3,5,1,2]size (int) =
5Returns (boolean)
falseSimulate the stack operations.
Push values from the pushed array one by one. After every push, keep popping while the top of the stack matches the next value required by the popped array.
At the end, if all values from popped were matched, the sequence is valid. Otherwise, it is not possible with normal stack behavior.
Pseudocode:
function validateStackPushPopSequence(pushed, popped, size):
stack = empty stack
popIndex = 0
for i from 0 to size - 1:
push pushed[i] into stack
while stack is not empty and stack top == popped[popIndex]:
pop from stack
popIndex++
return popIndex == sizeReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run