Leetcode 946. Validate Stack Sequences

Problem Explanation

This problem requires to validate if a sequence of integers that popped out from a stack is valid given the original sequence (pushed into the stack). We are provided with two sequences:

• The sequence of distinct values pushed into an initially empty stack.
• The expected sequence of values that should be popped from the stack.

The task is to determine if the expected popped sequence could be obtained from the given pushed sequence through a series of push and pop operations.

Example Walkthrough

Let's consider the following example:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

In the above example, we could have the following sequence of operations:

• push(1), push(2), push(3), push(4), pop() -> 4,
• push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

This series of push and pop operations result in the expected popped sequence. Therefore, the output should be true.

Approach

The approach used in the solution is pretty straightforward. The idea here is to for each number that we push into the stack, we'll check if it equals to the next number to be popped out from the 'popped' sequence. If they are equal, we'll pop it out from the stack. After we've pushed all the numbers into the stack, we check if the stack is empty or not. If the stack is empty, that means all the numbers from the 'pushed' sequence have been popped out in the correct order of the 'popped' sequence.

The technical details are as follows:

• Create a stack data structure.
• Initialize an index i to track the current position in the popped sequence.
• Loop over all numbers in the pushed sequence:
  • Push the current number into the stack.
  • While the stack is not empty and the top number of the stack equals to the current popped number, pop it out from the stack and increase the popped index by one.
• After the loop, if the stack is empty, that means all the numbers from the 'pushed' sequence have been popped out in the correct order. Therefore, return true. Otherwise, return false.

Python Solution

1
2python
3class Solution:
4    def validateStackSequences(self, pushed, popped) -> bool:
5        stack = []
6        i = 0
7        for x in pushed:
8            stack.append(x)
9            while stack and stack[-1] == popped[i]:
10                stack.pop()
11                i += 1
12        return not stack

Java Solution

1
2java
3class Solution {
4    public boolean validateStackSequences(int[] pushed, int[] popped) {
5        Stack<Integer> stack = new Stack<>();
6        int i = 0;
7        for (int x : pushed) {
8            stack.push(x);
9            while (!stack.empty() && stack.peek() == popped[i]) {
10                stack.pop();
11                i++;
12            }
13        }
14        return stack.empty();
15    }
16}

Javascript Solution

1
2javascript
3var validateStackSequences = function(pushed, popped) {
4    let stack = [];
5    let i = 0;
6    for (let x of pushed) {
7        stack.push(x);
8        while (stack.length > 0 && stack[stack.length - 1] === popped[i]) {
9            stack.pop();
10            i++;
11        }
12    }
13    return stack.length === 0;
14};

C++ Solution

1
2c++
3class Solution {
4public:
5    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
6        stack<int> stack;
7        int i = 0;  // popped's index
8
9        for (const int x : pushed) {
10          stack.push(x);
11          while (!stack.empty() && stack.top() == popped[i]) {
12            stack.pop();
13            ++i;
14          }
15        }
16
17        return stack.empty();
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public bool ValidateStackSequences(int[] pushed, int[] popped) {
5        Stack<int> stack = new Stack<int>();
6        int i = 0;
7        foreach(int x in pushed) {
8            stack.Push(x);
9            while(stack.Count > 0 && stack.Peek() == popped[i]) {
10                stack.Pop();
11                i++;
12            }
13        }
14        return stack.Count == 0;
15    }
16}

The solutions in all languages use a stack data structure to mimic the push and pop operations and an index i to track the current position in the popped sequence. The while loop inside the for loop is to keep popping out numbers from the stack if the top number of the stack equals the current number in the popped sequence. The result of the function is true if the stack is empty after the for loop.In conclusion, this algorithmic problem can be tackled using a stack data structure for mimicking the push and pop operations of the initial sequence, and an auxiliary index to track the position of the popped list. The solution given here uses this strategy for language-specific implementations in Python, Java, JavaScript, C++, and C#.

These languages were chosen due to their popularity and diverse styles: Python and JavaScript are common scripting languages, Java and C# are popular in enterprise software, while C++ is frequently used in systems programming, game development, and other performance-critical areas.

Regardless of the language used, the key to successfully solving this problem lies in understanding the mechanics of stack operations and how to manipulate them effectively to derive the required output. The ability to translate this understanding into any coding language is the mark of a proficient programmer. Whether you're using Python's list, Java's Stack class, or JavaScript's Array methods, the foundational concept remains the same. Acknowledging this can go a long way in enhancing your flexibility as a coder and in appreciating the universal attributes of programming.

Remember, the best way to learn is by doing. So take this solution as a base, tweak it, play with it, and try to reimplement it in your favorite programming language. Happy coding!