All problems

Validate Stack Sequences

Medium · stack

You have an empty stack and two lists of distinct integers, pushed and popped, which hold the same values in different orders.

You must push the values onto the stack in the order given by pushed, one each. Between pushes, and after the last one, you may pop the top of the stack whenever you like. The values you pop, in the order you pop them, must be exactly popped.

Return true if some sequence of pushes and pops produces popped, and false otherwise.

Examples

Example 1

Input: pushed = [1, 2, 3], popped = [2, 3, 1]

Output: true

Push 1, push 2, pop 2, push 3, pop 3, pop 1.

Example 2

Input: pushed = [1, 2, 3], popped = [3, 1, 2]

Output: false

To pop 3 first, 1 and 2 are pushed under it. Then 2 is on top of 1, so 1 cannot come out before 2.

Example 3

Input: pushed = [7, 8], popped = [7, 8]

Output: true

Push 7, pop 7, push 8, pop 8.

Constraints