Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/946.html

946. Validate Stack Sequences (Medium)

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: true
Explanation: 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: false
Explanation: 1 cannot be popped before 2.

 

Note:

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed is a permutation of popped.
4. pushed and popped have distinct values.

Related Topics:
Stack

Solution 1.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• C#
• RenderScript

• class Solution {
      public boolean validateStackSequences(int[] pushed, int[] popped) {
          Stack<Integer> stack = new Stack<Integer>();
          int length = pushed.length;
          int pushIndex = 0, popIndex = 0;
          while (pushIndex < length && popIndex < length) {
              stack.push(pushed[pushIndex]);
              pushIndex++;
              while (!stack.isEmpty() && stack.peek() == popped[popIndex]) {
                  stack.pop();
                  popIndex++;
              }
          }
          return stack.isEmpty();
      }
  }
  
  ############
  
  class Solution {
      public boolean validateStackSequences(int[] pushed, int[] popped) {
          Deque<Integer> stk = new ArrayDeque<>();
          int j = 0;
          for (int v : pushed) {
              stk.push(v);
              while (!stk.isEmpty() && stk.peek() == popped[j]) {
                  stk.pop();
                  ++j;
              }
          }
          return j == pushed.length;
      }
  }
  

• // OJ: https://leetcode.com/problems/validate-stack-sequences/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
          stack<int> s;
          int p = 0;
          for (int i : pushed) {
              s.push(i);
              while (s.size() && s.top() == popped[p]) {
                  s.pop();
                  ++p;
              }
          }
          return s.empty();
      }
  };
  

• class Solution:
      def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
          j, stk = 0, []
          for v in pushed:
              stk.append(v)
              while stk and stk[-1] == popped[j]:
                  stk.pop()
                  j += 1
          return j == len(pushed)
  
  ############
  
  class Solution(object):
      def validateStackSequences(self, pushed, popped):
          """
          :type pushed: List[int]
          :type popped: List[int]
          :rtype: bool
          """
          stack = []
          N = len(pushed)
          pi = 0
          for i in range(N):
              if stack and popped[i] == stack[-1]:
                  stack.pop()
              else:
                  while pi < N and pushed[pi] != popped[i]:
                      stack.append(pushed[pi])
                      pi += 1
                  pi += 1
          return not stack
  

• func validateStackSequences(pushed []int, popped []int) bool {
  	stk := []int{}
  	j := 0
  	for _, v := range pushed {
  		stk = append(stk, v)
  		for len(stk) > 0 && stk[len(stk)-1] == popped[j] {
  			stk = stk[:len(stk)-1]
  			j++
  		}
  	}
  	return j == len(pushed)
  }
  

• function validateStackSequences(pushed: number[], popped: number[]): boolean {
      const stk = [];
      let j = 0;
      for (const v of pushed) {
          stk.push(v);
          while (stk.length && stk[stk.length - 1] == popped[j]) {
              stk.pop();
              ++j;
          }
      }
      return j == pushed.length;
  }
  
  

• /**
   * @param {number[]} pushed
   * @param {number[]} popped
   * @return {boolean}
   */
  var validateStackSequences = function (pushed, popped) {
      let stk = [];
      let j = 0;
      for (const v of pushed) {
          stk.push(v);
          while (stk.length && stk[stk.length - 1] == popped[j]) {
              stk.pop();
              ++j;
          }
      }
      return j == pushed.length;
  };
  
  

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

• impl Solution {
      pub fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
          let mut stack = Vec::new();
          let mut i = 0;
          for &num in pushed.iter() {
              stack.push(num);
              while !stack.is_empty() && *stack.last().unwrap() == popped[i] {
                  stack.pop();
                  i += 1;
              }
          }
          stack.len() == 0
      }
  }
  
  

All Problems

All Solutions