LeetCode - Algorithms - 946. Validate Stack Sequences

Problem

946. Validate Stack Sequences

Analysis

Forbidden triple for stack generability

© https://algs4.cs.princeton.edu/13stacks/

a permutation can be generated by a stack if and only if it has no forbidden triple (a, b, c) such that a < b < c with c first, a second, and b third (possibly with other intervening integers between c and a and between a and b).

Java

Greedy

© Validate Stack Sequences

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int j = 0;
        for (int i = 0; i < pushed.length; i++) {
            stack.addFirst(pushed[i]);
            while (!stack.isEmpty() && stack.peekFirst() == popped[j]) {
                stack.removeFirst();
                j++;
            }
        }
        if (stack.isEmpty())
            return true;
        else
            return false;        
    }
}

Submission Detail

  • 152 / 152 test cases passed.
  • Runtime: 1 ms, faster than 93.97% of Java online submissions for Validate Stack Sequences.
  • Memory Usage: 38.4 MB, less than 90.26% of Java online submissions for Validate Stack Sequences.

no stack

© no stack solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0;
        for (int k = 0, j = 0; k < pushed.length; k++) {
            pushed[i] = pushed[k];
            while (i >= 0 && pushed[i] == popped[j]) {
                i--;
                j++;
            }
            i++;
        }
        return i == 0;       
    }
}

Submission Detail

  • 152 / 152 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Stack Sequences.
  • Memory Usage: 38.9 MB, less than 18.73% of Java online submissions for Validate Stack Sequences.