Jobs

Interviews

Discussions

Validate Stack Sequences

Medium

Asked by:

More companies

57 views

Topics:

ArraysStacks

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.

Try coding it in LeetCode

Validate Stack Sequences

Medium

Asked by:

57 views

Topics:

ArraysStacks

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `pushed` and `popped` arrays? Can I assume they are integers?
Can the `pushed` and `popped` arrays contain duplicate values?
If the `popped` sequence is not a valid sequence based on the `pushed` sequence, what should the return value be? Should I return `false`, throw an exception, or something else?
Are the `pushed` and `popped` arrays guaranteed to have the same length?
Can either the `pushed` or `popped` array be empty or null?

Brute Force Solution

Approach

The brute force method for this puzzle involves simulating every single possible sequence of pushing elements onto a stack and then popping them off. We then check if any of these sequences results in the desired output sequence. It's like trying every possible path to see if we can reach the correct destination.

Here's how the algorithm would work step-by-step:

Start by considering all possible orders in which you could push and pop elements.
For each of these possible orders, simulate the stack operations (pushing and popping) according to that order.
After each push or pop, check if the sequence of popped elements so far matches the beginning of the desired output sequence.
If, at any point, the popped elements don't match, abandon that sequence of pushes and pops and try a different one.
If you find a sequence of pushes and pops that produces the entire desired output sequence, then you know the output is a valid stack sequence.

Code Implementation

def validate_stack_sequences_brute_force(pushed, popped):
    number_pushed = len(pushed)
    number_popped = len(popped)

    if number_pushed != number_popped:
        return False

    import itertools
    for operations in itertools.product([0, 1], repeat=2 * number_pushed):
        stack = []
        pushed_index = 0
        popped_index = 0
        possible = True

        for operation in operations:
            if operation == 0:
                # Simulate push operation if available
                if pushed_index < number_pushed:
                    stack.append(pushed[pushed_index])
                    pushed_index += 1
                else:
                    possible = False
                    break
            else:
                # Simulate pop operation if possible
                if stack:

                    if stack[-1] == popped[popped_index]:
                        stack.pop()
                        popped_index += 1
                    else:
                        possible = False
                        break
                else:
                    possible = False
                    break

        # Check if we successfully popped every element
        if possible and popped_index == number_popped:
            return True

    return False

Big(O) Analysis

Time Complexity

O(2^(2n)) – The brute force approach involves exploring all possible sequences of push and pop operations. For n pushed elements, there are 2n total operations (n pushes and n pops). Each operation has two choices (push or pop if the stack isn't empty and elements remain to be pushed). Therefore, there are 2^(2n) possible sequences of pushes and pops to explore. Each sequence takes O(n) time to simulate, leading to an overall time complexity that is dominated by the number of possible sequences. Thus, the time complexity is O(2^(2n)).

Space Complexity

O(N) – The brute force approach, as described, simulates push and pop operations on a stack. This simulation requires a stack data structure to store the pushed elements. In the worst-case scenario, all N elements of the pushed array might be pushed onto the stack before any are popped. Therefore, the auxiliary space needed for the stack is proportional to the number of elements in the pushed array, which is N. Thus, the space complexity is O(N).

Optimal Solution

Approach

We simulate the pushing and popping operations on a stack. The key is to use a real stack to track what’s been pushed and see if we can pop it off when needed, matching the order of the 'popped' sequence. This avoids needing to explore all possible stack operations.

Here's how the algorithm would work step-by-step:

Imagine having a real stack, similar to a pile of plates.
Go through the 'pushed' sequence one item at a time, pushing each onto the stack.
After pushing an item, check if the top of the stack matches the next item we're supposed to 'pop'.
If it matches, 'pop' the item from the stack and move to the next item in the 'popped' sequence. Keep doing this until the stack is empty or the top item doesn't match.
Continue pushing and popping based on whether the stack's top matches the next item to be popped.
At the end, if the stack is empty, it means the 'popped' sequence is a valid result of the 'pushed' sequence. If the stack isn't empty, it's not a valid sequence.

Code Implementation

def validate_stack_sequences(pushed, popped):
    stack = []
    popped_index = 0

    for push_element in pushed:
        stack.append(push_element)

        # Check if the top of the stack matches the next element to pop
        while stack and stack[-1] == popped[popped_index]:

            # Pop elements as long as they match the popped sequence.
            stack.pop()
            popped_index += 1

    # If the stack is empty, it's a valid sequence
    return not stack

Big(O) Analysis

Time Complexity

O(n) – We iterate through the 'pushed' array of size n, pushing each element onto the stack once. While pushing, we also check if the top of the stack matches the next element in the 'popped' array. The popping operation within the while loop occurs at most n times because each element is pushed and popped at most once. Therefore, the dominant operation is iterating through the 'pushed' array, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm simulates stack operations using a real stack data structure. In the worst-case scenario, all elements from the 'pushed' array may be pushed onto the stack before any elements are popped. Therefore, the stack's size can grow up to N, where N is the number of elements in the 'pushed' array. Thus, the auxiliary space required is proportional to N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
pushed or popped array is null or empty	Return True if both are empty, otherwise handle null array gracefully by returning False to avoid NullPointerException.
pushed array is shorter than popped array	Return False since you can't pop more elements than were pushed.
pushed array contains duplicate values	The algorithm should still correctly validate if duplicates are handled appropriately in the stack operations.
pushed and popped arrays are identical	This represents a valid stack sequence where elements are pushed and immediately popped, and algorithm should return True if order matches.
pushed array is in descending order, popped array is in ascending order	This is a valid but potentially inefficient scenario; the stack will grow to its maximum size before elements are popped, which algorithm should handle.
No valid sequence exists (popped array is impossible given pushed array)	The algorithm should correctly identify and return False when the popped sequence cannot be formed from the pushed sequence.
Maximum array size allowed by memory constraints	Ensure the stack doesn't exceed memory limits as the size of the pushed array increases by optimizing stack operations if possible.
Arrays contain large integer values that might cause integer overflow	The algorithm uses comparison operations only, and no arithmetic, so integer overflow is not a concern.

pushed or popped array is null or empty

How to Handle:

Return True if both are empty, otherwise handle null array gracefully by returning False to avoid NullPointerException.

pushed array is shorter than popped array

How to Handle:

Return False since you can't pop more elements than were pushed.

pushed array contains duplicate values

How to Handle:

The algorithm should still correctly validate if duplicates are handled appropriately in the stack operations.

pushed and popped arrays are identical

How to Handle:

This represents a valid stack sequence where elements are pushed and immediately popped, and algorithm should return True if order matches.

pushed array is in descending order, popped array is in ascending order

How to Handle:

This is a valid but potentially inefficient scenario; the stack will grow to its maximum size before elements are popped, which algorithm should handle.

No valid sequence exists (popped array is impossible given pushed array)

How to Handle:

The algorithm should correctly identify and return False when the popped sequence cannot be formed from the pushed sequence.

Maximum array size allowed by memory constraints

How to Handle:

Ensure the stack doesn't exceed memory limits as the size of the pushed array increases by optimizing stack operations if possible.

Arrays contain large integer values that might cause integer overflow

How to Handle:

The algorithm uses comparison operations only, and no arithmetic, so integer overflow is not a concern.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `pushed` and `popped` arrays? Can I assume they are integers?
Can the `pushed` and `popped` arrays contain duplicate values?
If the `popped` sequence is not a valid sequence based on the `pushed` sequence, what should the return value be? Should I return `false`, throw an exception, or something else?
Are the `pushed` and `popped` arrays guaranteed to have the same length?
Can either the `pushed` or `popped` array be empty or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering all possible orders in which you could push and pop elements.
For each of these possible orders, simulate the stack operations (pushing and popping) according to that order.
After each push or pop, check if the sequence of popped elements so far matches the beginning of the desired output sequence.
If, at any point, the popped elements don't match, abandon that sequence of pushes and pops and try a different one.
If you find a sequence of pushes and pops that produces the entire desired output sequence, then you know the output is a valid stack sequence.

Code Implementation

def validate_stack_sequences_brute_force(pushed, popped):
    number_pushed = len(pushed)
    number_popped = len(popped)

    if number_pushed != number_popped:
        return False

    import itertools
    for operations in itertools.product([0, 1], repeat=2 * number_pushed):
        stack = []
        pushed_index = 0
        popped_index = 0
        possible = True

        for operation in operations:
            if operation == 0:
                # Simulate push operation if available
                if pushed_index < number_pushed:
                    stack.append(pushed[pushed_index])
                    pushed_index += 1
                else:
                    possible = False
                    break
            else:
                # Simulate pop operation if possible
                if stack:

                    if stack[-1] == popped[popped_index]:
                        stack.pop()
                        popped_index += 1
                    else:
                        possible = False
                        break
                else:
                    possible = False
                    break

        # Check if we successfully popped every element
        if possible and popped_index == number_popped:
            return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine having a real stack, similar to a pile of plates.
Go through the 'pushed' sequence one item at a time, pushing each onto the stack.
After pushing an item, check if the top of the stack matches the next item we're supposed to 'pop'.
If it matches, 'pop' the item from the stack and move to the next item in the 'popped' sequence. Keep doing this until the stack is empty or the top item doesn't match.
Continue pushing and popping based on whether the stack's top matches the next item to be popped.
At the end, if the stack is empty, it means the 'popped' sequence is a valid result of the 'pushed' sequence. If the stack isn't empty, it's not a valid sequence.

Code Implementation

def validate_stack_sequences(pushed, popped):
    stack = []
    popped_index = 0

    for push_element in pushed:
        stack.append(push_element)

        # Check if the top of the stack matches the next element to pop
        while stack and stack[-1] == popped[popped_index]:

            # Pop elements as long as they match the popped sequence.
            stack.pop()
            popped_index += 1

    # If the stack is empty, it's a valid sequence
    return not stack

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
pushed or popped array is null or empty	Return True if both are empty, otherwise handle null array gracefully by returning False to avoid NullPointerException.
pushed array is shorter than popped array	Return False since you can't pop more elements than were pushed.
pushed array contains duplicate values	The algorithm should still correctly validate if duplicates are handled appropriately in the stack operations.
pushed and popped arrays are identical	This represents a valid stack sequence where elements are pushed and immediately popped, and algorithm should return True if order matches.
pushed array is in descending order, popped array is in ascending order	This is a valid but potentially inefficient scenario; the stack will grow to its maximum size before elements are popped, which algorithm should handle.
No valid sequence exists (popped array is impossible given pushed array)	The algorithm should correctly identify and return False when the popped sequence cannot be formed from the pushed sequence.
Maximum array size allowed by memory constraints	Ensure the stack doesn't exceed memory limits as the size of the pushed array increases by optimizing stack operations if possible.
Arrays contain large integer values that might cause integer overflow	The algorithm uses comparison operations only, and no arithmetic, so integer overflow is not a concern.

pushed or popped array is null or empty

How to Handle:

Return True if both are empty, otherwise handle null array gracefully by returning False to avoid NullPointerException.

pushed array is shorter than popped array

How to Handle:

Return False since you can't pop more elements than were pushed.

pushed array contains duplicate values

How to Handle:

The algorithm should still correctly validate if duplicates are handled appropriately in the stack operations.

pushed and popped arrays are identical

How to Handle:

This represents a valid stack sequence where elements are pushed and immediately popped, and algorithm should return True if order matches.

pushed array is in descending order, popped array is in ascending order

How to Handle:

This is a valid but potentially inefficient scenario; the stack will grow to its maximum size before elements are popped, which algorithm should handle.

No valid sequence exists (popped array is impossible given pushed array)

How to Handle:

The algorithm should correctly identify and return False when the popped sequence cannot be formed from the pushed sequence.

Maximum array size allowed by memory constraints

How to Handle:

Ensure the stack doesn't exceed memory limits as the size of the pushed array increases by optimizing stack operations if possible.

Arrays contain large integer values that might cause integer overflow

How to Handle:

The algorithm uses comparison operations only, and no arithmetic, so integer overflow is not a concern.