Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

946. Validate Stack Sequences

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> stack;
    int i = 0;  // popped's index

    for (const int x : pushed) {
      stack.push(x);
      while (!stack.empty() && stack.top() == popped[i]) {
        stack.pop();
        ++i;
      }
    }

    return stack.empty();
  }
};




			


class Solution {
  public boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stack = new ArrayDeque<>();
    int i = 0; // popped's index

    for (final int x : pushed) {
      stack.push(x);
      while (!stack.isEmpty() && stack.peek() == popped[i]) {
        stack.pop();
        ++i;
      }
    }

    return stack.isEmpty();
  }
}




			


class Solution:
  def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
    stack = []
    i = 0  # popped's index

    for x in pushed:
      stack.append(x)
      while stack and stack[-1] == popped[i]:
        stack.pop()
        i += 1

    return not stack