{x}
blog image

Build an Array With Stack Operations

You are given an integer array target and an integer n.

You have an empty stack with the two following 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"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Read 3 from the stream and push it to the stack. s = [1,2,3].

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Since the stack (from the bottom to the top) is equal to target, we stop the stack operations.
The answers that read integer 3 from the stream are not accepted.

 

Constraints:

  • 1 <= target.length <= 100
  • 1 <= n <= 100
  • 1 <= target[i] <= n
  • target is strictly increasing.

Solution Explanation for Building an Array with Stack Operations

This problem involves constructing a target array using stack operations ("Push" and "Pop") and a stream of integers from 1 to n. The goal is to find the sequence of stack operations that builds the target array.

Approach:

The solution uses a single loop iterating through the target array. For each element in target, it checks if the current number in the simulated stream (cur) is less than the target element. If it is, "Push" and "Pop" operations are added to the result list until cur reaches the target element. Then a "Push" operation is added to push the target element onto the stack.

Time Complexity Analysis:

The code iterates through the target array once. In the worst case, the inner while loop iterates n times for each element in target. Therefore, the overall time complexity is O(n * m), where 'n' is the value of the input n and 'm' is the length of the target array. However, since the target array is strictly increasing, the total number of iterations of the inner while loop across all iterations of the outer loop cannot exceed n. Therefore, a more accurate and tighter upper bound on the time complexity is O(n).

Space Complexity Analysis:

The space complexity is dominated by the size of the ans list (or equivalent data structure in other languages), which stores the sequence of stack operations. In the worst case, the length of this list can be 2 * len(target). Thus, the space complexity is O(m), where 'm' is the length of the target array.

Code Explanation (Python):

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        cur, ans = 0, []  # Initialize current number and results list
        for v in target: #Iterate through target array
            cur += 1 #Increment current number
            while cur < v: #Check if cur needs to catch up to the target element v
                ans.extend(['Push', 'Pop']) #Append Push and Pop operations
                cur += 1 #Increment cur
            ans.append('Push') #Append Push operation for the target element
        return ans

The code in other languages follows the same logic with minor syntactic differences. The core idea remains the same, offering an efficient and concise solution to the problem.