By Long Luo

This article is the solution 4 Approaches: Stack, Array, Greedy and O(n) Time O(1) Space of Problem 946. Validate Stack Sequences.

Intuition

All elements must be pushed in in order. The key is how to pop them out?

Assuming that the value of the current top element of the stack is \(1\), and the next value to be popped in the corresponding popped sequence is also \(1\), then this value must be popped out immediately. Because the subsequent push will change the top element of the stack to a value other than \(2\), so the popped sequence of the popped numbers does not correspond.

Pushes each number in the pushed queue onto the stack, checking to see if the number is the next value to be popped in the popped sequence, and pops it if so.

Finally, check that not all the popped values are popped.

Stack

We can use a Stack to simulate the process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (popped == null || pushed.length <= 1) {
        return true;
    }

    int len = pushed.length;
    int popIdx = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < len; i++) {
        stack.push(pushed[i]);
        while (!stack.empty() && popIdx < len && stack.peek() == popped[popIdx]) {
            stack.pop();
            popIdx++;
        }
    }

    return popIdx == len;
}

Analysis

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Stack

The Stack approach uses \(2\) loops which make it hard to understand.

We can simulate the operation. We use \(2\) indices to the pushed and poped array.

There comes \(3\) cases:

1. \(pushed[i] \ne poped[j]\), \(i++\)
2. \(pushed[i] = poped[j]\), \(i++\), \(j++\)
3. \(i = len\), \(popped[j] = stack.peek()\), \(j++\),
4. \(i = len\), \(j \lt len\), \(popped[j] = stack.peek()\), then break the circle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public static boolean validateStackSequences(int[] pushed, int[] popped) {
    if (popped == null || pushed.length <= 1) {
        return true;
    }

    int len = pushed.length;
    int pushIdx = 0;
    int popIdx = 0;
    Stack<Integer> stack = new Stack<>();
    while (popIdx < len) {
        while (pushIdx < len && pushed[pushIdx] != popped[popIdx]) {
            stack.push(pushed[pushIdx]);
            pushIdx++;
        }

        while (pushIdx < len && popIdx < len && pushed[pushIdx] == popped[popIdx]) {
            pushIdx++;
            popIdx++;
        }

        while (!stack.empty() && popped[popIdx] == stack.peek()) {
            popIdx++;
            stack.pop();
        }

        if (pushIdx == len && popIdx < len && popped[popIdx] != stack.peek()) {
            break;
        }
    }

    if (stack.empty()) {
        return true;
    }

    return false;
}

Analysis

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Array

Use the array to realize the function of the stack, and simulate the operation of popping and pushing the stack. size represents the size of the stack, and size-1 is the position of the top of the stack.

Although access is faster, using an array to implement a stack is not recommended in most cases.

Especially when the pushed array may be very large, the array stack as the stack will also be very large.

But in fact, there are not many elements in the stack at the same time, which is a great waste.

1
2
3
4
5
6
7
8
9
10
11

public boolean validateStackSequences(int[] pushed, int[] popped) {
    int[] stack = new int[pushed.length];
    int size = 0;
    for (int i = 0, j = 0; i < pushed.length; i++) {
        stack[size++] = pushed[i];
        while (size != 0 && stack[size - 1] == popped[j]) {
            size--;j++;
        }
    }
    return size == 0;
}

Analysis

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

O(n) Time O(1) Space

In fact, we can optimize the Solution \(3\), we can find that stack is redundant.

When traversing the pushed array, \(pushed[i]\) is actually the element at the top of the stack.

At this time, \(pushed[i-1]\), \(push[i-2]\)… These positions are already “free”, so they are completely The role of stack can be replaced by array push.

1
2
3
4
5
6
7
8
9
10
11
12

public boolean validateStackSequences(int[] pushed, int[] popped) {
    int size = 0;
    for (int i = 0, j = 0; i < pushed.length; i++) {
        pushed[size++] = pushed[i];
        while (size != 0 && pushed[size - 1] == popped[j]) {
            size--;
            j++;
        }
    }

    return size == 0;
}

Analysis

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗