DIY: Validate Stack Sequences

Solve the interview question "Validate Stack Sequences" yourself in this lesson.

Problem statement

You are provided with two stack sequences, pushed and popped, with distinct values. Return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Input

The input will be two lists. The following is an example input:

pushed = [1,2,3,4,5]
popped = [1,2,3,4,5]

Output

The output will be a Boolean representing whether these sequences of push and pop operations could have been interleaved and performed on a valid stack that was initially empty. The following is an example output:

true

The following operation would result in an empty stack:

push(1), pop(1), push(2), pop(2), push(3), pop(3), push(4), pop(4), push(5), pop(5)

Coding exercise

Implement the validate_stack_sequences(pushed, popped) function, where pushed and popped are the two stack sequences. The function returns either true or false depending on whether the stack was initially empty or not.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.