Given two 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.

**Example 1:**

Input:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]Output:trueExplanation:We might do the following sequence: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

**Example 2:**

Input:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]Output:falseExplanation:1 cannot be popped before 2.

**Note:**

`0 <= pushed.length == popped.length <= 1000`

`0 <= pushed[i], popped[i] < 1000`

`pushed`

is a permutation of`popped`

.`pushed`

and`popped`

have distinct values.

## Solution

public class Solution { public bool ValidateStackSequences(int[] pushed, int[] popped) { Stack<int> s = new Stack<int>(); int j = 0; foreach(int num in pushed){ s.Push(num); while(s.Count > 0 && j < pushed.Length && s.Peek() == popped[j]){ s.Pop(); j++; } } return j == popped.Length; } }

Time Complexity: O(n)

Space Complexity: O(n)