Build an Array With Stack Operations

Medium

Google

2 views

Topics:

StacksArrays

You are given an integer array target and an integer n. You have an empty stack with the following two operations:

"Push": pushes an integer to the top of the stack.
"Pop": removes the integer on the top of the stack.

You also have a stream of the integers in the range [1, n].

Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:

If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
If the stack is not empty, pop the integer at the top of the stack.
If, at any moment, the elements in the stack (from the bottom to the top) are equal to target, do not read new integers from the stream and do not do more operations on the stack.

Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]

Can you provide an algorithm to determine the list of operations required to build the target array from the stream of integers, while adhering to the specified stack operations?

Build an Array With Stack Operations

Medium

Google

2 views

Topics:

StacksArrays

You are given an integer array target and an integer n. You have an empty stack with the following two operations:

"Push": pushes an integer to the top of the stack.
"Pop": removes the integer on the top of the stack.

You also have a stream of the integers in the range [1, n].

Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:

If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
If the stack is not empty, pop the integer at the top of the stack.
If, at any moment, the elements in the stack (from the bottom to the top) are equal to target, do not read new integers from the stream and do not do more operations on the stack.

Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]

Can you provide an algorithm to determine the list of operations required to build the target array from the stream of integers, while adhering to the specified stack operations?

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 for `n` and the elements in `target`?
Will the `target` array always be strictly increasing and contain only positive integers?
If it's impossible to construct the `target` array using push and pop operations, what should I return? An empty list, null, or throw an exception?
Is there a memory constraint for the operations list I am building?
Can `target` be empty?

Brute Force Solution

Approach

The problem is like having a stream of numbers and figuring out how to create a specific target sequence using only 'push' and 'pop' operations on a stack. The brute force approach explores every possible combination of pushing numbers from the stream onto a stack and then potentially popping them off.

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

Start with an empty stack and an empty list of operations.
Consider the first number from the stream. Try pushing it onto the stack.
Now, from the stack, consider two options: either pop the number off or leave it on the stack.
For each of those options, check if the sequence of popped numbers so far matches the beginning of the target sequence.
If it does not match, abandon that series of push and pop operations.
If it matches, and we haven't completed the target sequence, grab the next number from the stream. Push it onto the stack and again consider the two options of either popping it off or not.
Repeat these steps until we've either found a sequence of operations that builds the target sequence perfectly, or we've exhausted all possibilities.
If we find a valid sequence, store it as a potential solution.
If we exhaust all numbers and stack options without finding the target sequence, then no solution exists.

Code Implementation

def build_array_with_stack_operations(target_array, number_limit):
    operations_list = []

    def backtrack(index, current_stack, current_operations):
        if index == len(target_array):
            return True

        if len(current_operations) > 3 * number_limit:
            return False

        stream_number = len(current_operations) // 2 + 1

        if stream_number <= number_limit:
            # Try pushing the next number from the stream
            if backtrack_push(index, current_stack, current_operations, stream_number):
                return True
        
        if current_stack:
            # Try popping from the stack if it's not empty
            if backtrack_pop(index, current_stack, current_operations):
                return True

        return False

    def backtrack_push(index, current_stack, current_operations, stream_number):
        current_stack.append(stream_number)
        current_operations.append("Push")

        if backtrack(index, current_stack, current_operations):
            return True
        else:
            # Backtrack: undo the push operation
            current_stack.pop()
            current_operations.pop()
            return False

    def backtrack_pop(index, current_stack, current_operations):
        popped_element = current_stack.pop()

        # Only continue if the popped element matches the target
        if popped_element == target_array[index]:
            current_operations.append("Pop")

            # Advance in the target array
            if backtrack(index + 1, current_stack, current_operations):
                return True
            else:
                # Backtrack: undo the pop operation
                current_stack.append(popped_element)
                current_operations.pop()
                return False
        else:
            # If the popped element doesn't match, restore the stack
            current_stack.append(popped_element)
            return False

    if backtrack(0, [], operations_list):
        return operations_list
    else:
        return []

Big(O) Analysis

Time Complexity

O(2^n) – The described brute-force approach explores all possible combinations of 'push' and 'pop' operations for each number in the input stream of size n. For each number, we have two choices: push then pop, or push and leave on the stack. This creates a binary decision tree where each level represents a number from the stream. Therefore, the total number of paths to explore grows exponentially with n, resulting in approximately 2^n operations. The algorithm explores a decision tree where at each level there are two branches to follow, 'push and pop' and 'push and leave on the stack'.

Space Complexity

O(N) – The auxiliary space complexity is dominated by the call stack due to the recursive nature of exploring different push and pop combinations. In the worst-case scenario, we might push all N numbers from the stream onto the stack before exploring pop operations extensively. This leads to a maximum recursion depth proportional to N, where N is the number of elements in the stream. Therefore, the space used by the recursion stack grows linearly with the input size N.

Optimal Solution

Approach

We want to mimic pushing numbers onto a stack and popping them off, but only to create a specific target sequence. The smart way to do this is to build up the stack in order, but only push numbers when they're needed in the target, and skip any numbers we don't need.

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

Start with the first number we need in our target sequence.
Imagine filling a stack by pushing in consecutive natural numbers(1,2,3,...).
For each number, check: Is this number the one we're looking for next in the target sequence? If so, push it onto the stack, and then immediately pop it off and advance to the next target number.
If the current number isn't the number we need, push it onto the stack, but do not pop it off, and simply move to the next number.
Keep pushing and popping until we've reached the end of the target sequence.

Code Implementation

def build_array_with_stack_operations(target_sequence, number):    operations_list = []
    target_index = 0

    for current_number in range(1, number + 1):
        # If we've completed the target, exit.
        if target_index == len(target_sequence):
            break

        # Always push the current number.
        operations_list.append("Push")

        # Check if the current number matches.
        if target_sequence[target_index] == current_number:
            # If it matches, pop and advance.
            operations_list.append("Pop")
            target_index += 1
        else:
            # Current number is not needed in target.
            operations_list.append("Pop")

    return operations_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through a sequence of numbers from 1 up to n, where n is implicitly determined by the target array and represents the largest possible number that could be pushed onto the stack. For each number in this sequence, it performs a constant amount of work: it checks if the number is the next element in the target sequence, and then either pushes and pops (two operations) or just pushes (one operation). Since the number of iterations is directly proportional to n and the operations within each iteration are constant, the time complexity is O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from the list of operations (push and pop) that are recorded. In the worst-case scenario, where every number from 1 to n (the implicit upper limit based on the target sequence) needs to be pushed and popped, the list can grow linearly with the implicit input size n. Therefore, the auxiliary space used by the algorithm is proportional to the size of the target sequence. Hence, the space complexity is O(N), where N is the largest number that could be pushed onto the stack, which is implicitly related to the size of target.

Edge Cases

Case	How to Handle
Empty target array	Return an empty list since there is nothing to build.
n is zero or negative	Return an empty list as there's no valid range of numbers to consider.
target array contains numbers outside the range [1, n]	Filter the target array to only include numbers within the valid range before proceeding to avoid out-of-bound Push operations.
Target array is already in ascending order from 1 to n	The solution will push and pop appropriately to build the list.
No combination of Push and Pop operations can generate the target array	The code should iterate through numbers 1 to n and add the 'Push' operations, only adding Pop if the current number is not in the target array.
n is smaller than the largest number in the target array	Treat n as if it equals the maximum value present in the target array for operational correctness and avoiding indexOutOfBounds.
Large n leading to excessive memory usage if not carefully handled.	The algorithm's linear time and space complexity will generally scale well, but extremely large n values may necessitate further memory optimization if memory limits are a concern.
target is null	Throw an IllegalArgumentException as the program cannot function without a target array.