[Leetcode][946. Validate Stack Sequences] 4 Approaches: Stack, Array and Greedy

By Long Luo

This article is the solution of Problem 946. Validate Stack Sequences.

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
946. Validate Stack Sequences

Medium

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

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.

Constraints:
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
All the elements of pushed are unique.
popped.length == pushed.length
popped is a permutation of pushed.

Solution 1 Using Stack and Greedy

Idea

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.

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)O(N)
  • Space Complexity: O(N)O(N)

Solution 2 Using Stack

Solution 1 uses 2 circles and 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] != poped[j], i++
  2. pushed[i] == poped[j], i++, j++
  3. i == len, popped[j] == stack.peek(), j++
  4. i == len, j < len, popped[j] == stack.peek() --> break the circle.

Code

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)O(N)
  • Space Complexity: O(N)O(N)

Solution 3 Using 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)O(N)
  • Space Complexity: O(N)O(N)

Solution 4 Optimize Method 3

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)O(N)
  • Space Complexity: O(1)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. 😉😃💗