Build an Array With Stack Operations – Python Solution

Problem Description

So, you want to build an array using stack operations? Sounds easy, right? Well, let’s just say it’s like trying to organize your sock drawer while blindfolded. The task is to construct an array from 1 to n using two operations: “Push” (to add an element to the stack) and “Pop” (to remove the top element from the stack). The catch? You can only push numbers in sequential order, and you need to match a given target array.

Imagine you’re at a buffet, and you can only take food in a specific order. You can grab a plate (Push) but if you realize you don’t want that mystery meat (Pop), you have to put it back. The goal is to end up with a plate full of your favorite dishes (the target array) without making a mess of the buffet line!

Code Solution


class Solution:
    def buildArray(self, target: list[int], n: int) -> list[str]:
        ans = []
        i = 0  # Target pointer
        num = 1  # Curr num

        while i < len(target):
            t = target[i]
            if t == num:
                ans.append('Push')
                i += 1
            else:
                ans.append('Push')
                ans.append('Pop')
            num += 1

        return ans

Approach

The approach is straightforward: we iterate through the target array while keeping track of the current number we are supposed to push. If the current number matches the target, we simply "Push" it onto the stack. If it doesn’t match, we "Push" it and then "Pop" it right back out. This way, we ensure that we only keep the numbers that are in the target array.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(m), where m is the length of the target array. We only iterate through the target once.
Space Complexity	O(m), for storing the operations in the answer list.

Real-World Example

Think of it like a game of Jenga. You can only add blocks (Push) in a specific order, and if you realize that the block you just added doesn’t fit your tower (the target array), you have to take it out (Pop). The goal is to build the tallest tower possible without toppling it over!