633. Validate Stack Sequences

Given two sequences pushed and popped, each a permutation of the same distinct values, determine whether the popped sequence could result from a valid series of push and pop operations on an initially empty stack that pushes values in the pushed order. Return true or false. The input is JSON {pushed, popped}.

Input: JSON {pushed, popped}.

Output: Boolean — true or false.

Examples

Input: {"pushed":[1,2,3,4,5],"popped":[4,5,3,2,1]}
Output: true
Explanation: A valid push/pop interleaving exists.

Input: {"pushed":[1,2,3,4,5],"popped":[4,3,5,1,2]}
Output: false
Explanation: No valid sequence produces this.

Input: {"pushed":[1],"popped":[1]}
Output: true
Explanation: Trivially valid.

Constraints

• 1<=n<=1000
• distinct values

Asked by