1441. Build an Array With Stack Operations
Model: qwen2.5-coder:14b
Topics: Stack
FAANG asked: 1
Acceptance rate: 70.4%
Problem Breakdown
The problem requires us to build a target array using a stack-like approach with two operations: “Push” and “Pop”. We are given an array target and an integer n. The numbers from 1 to n are read sequentially, and we must use the “Push” operation to add each number to our current array. If the number is not in the target array, we immediately follow with a “Pop” operation to remove it. We stop reading numbers once we have built the target array exactly.
Inputs:
target: An array of integers that needs to be constructed.n: An integer representing the range of numbers from which we can read.
Outputs:
- A list of strings representing the sequence of “Push” and “Pop” operations needed to build the target array.
Implicit Constraints or Tricky Edge Cases:
- The target array is strictly increasing, meaning no duplicates.
- If
nis larger than the largest number in the target array, we only need to consider up to the largest number in the target array. - The target array can be empty, which would require no operations.
Intuition
A brute-force approach would involve iterating through numbers from 1 to n, pushing each number onto a stack, and then popping it if it’s not in the target array. This approach is inefficient because it performs unnecessary “Push” and “Pop” operations for numbers that are not needed.
The key insight is to recognize that we only need to consider up to the largest number in the target array. We can iterate through the target array directly, pushing each number and then checking if the next number in sequence should also be pushed or popped based on whether it appears in the target array.
Approach
- Initialize an empty list
operationsto store the sequence of operations. - Use a pointer
ito track our current position in the target array, starting at 0. - Iterate through numbers from 1 to
n:- If
iis equal to the length of the target array, break out of the loop as we have built the target array. - Append “Push” to
operations. - If the current number does not match the target[i], append “Pop” to
operations. - If the current number matches the target[i], increment
ito move to the next target element.
- If
- Return the list of operations.
Complexity Analysis
- Time Complexity: O(n), where n is the given integer. We iterate through numbers from 1 to n once.
- Space Complexity: O(m), where m is the length of the target array. This is for storing the operations list, which in the worst case can be twice the length of the target array (all “Push” and “Pop”).
Solution
def buildArray(target, n):
operations = []
i = 0
for num in range(1, n + 1):
if i == len(target):
break
operations.append("Push")
if target[i] != num:
operations.append("Pop")
else:
i += 1
return operations
Edge Cases Handled
- Empty Target Array: If the target array is empty, the loop will not execute, and an empty list of operations will be returned.
- n Larger than Largest Number in Target: The loop will stop once the target array is built, even if
nis larger than the largest number in the target array.