Leetcode 1441: Build an Array With Stack Operations
You are given a strictly increasing integer array
target and an integer n. Starting with an empty stack, you can perform two operations: ‘Push’ to add an integer to the stack and ‘Pop’ to remove the top element from the stack. A stream of integers from 1 to n is provided. Use the stack operations to build the stack so that it contains the elements of target in order (from bottom to top). Return the sequence of operations required. Stop processing once the stack equals the target array.Problem
Approach
Steps
Complexity
Input: An array of integers `target` and an integer `n`.
Example: Input: target = [2,4,5], n = 6
Constraints:
• 1 <= target.length <= 100
• 1 <= n <= 100
• 1 <= target[i] <= n
• target is strictly increasing.
Output: A list of strings representing the stack operations required to build `target`.
Example: Output: ["Push", "Pop", "Push", "Push", "Push"]
Constraints:
• The operations should correctly build the stack to match `target`.
Goal: Generate the sequence of operations ('Push' and 'Pop') to transform the stack to match `target`.
Steps:
• Initialize an empty list `ans` to store the operations.
• Iterate through the stream of integers from 1 to `n`.
• For each integer, check if it is in `target`.
• If it is in `target`, perform a 'Push' operation.
• If it is not in `target`, perform both a 'Push' and a 'Pop' operation to remove it immediately.
• Stop processing once all elements of `target` are pushed into the stack.
Goal: The solution must simulate stack operations accurately and stop as soon as the stack matches the `target`.
Steps:
• The operations must be performed sequentially.
• Only integers from the stream should be used.
Assumptions:
• `target` is strictly increasing.
• `n` is large enough to cover all elements in `target`.
• Input: Input: target = [2,4,6], n = 6
• Explanation: Operations: Push 1 and Pop it (not in target), Push 2 (in target), Push 3 and Pop it (not in target), Push 4 (in target), Push 5 and Pop it (not in target), Push 6 (in target). Output: ["Push", "Pop", "Push", "Push", "Pop", "Push", "Push", "Pop", "Push"].
Approach: Use a single loop to traverse integers from 1 to `n` and simulate stack operations based on whether each integer is in `target`.
Observations:
• The stack operations must maintain the order of `target`.
• Extra integers not in `target` should be handled with a 'Push' followed by a 'Pop'.
• Simulating operations sequentially ensures that the stack matches `target` without skipping any integers in the stream.
Steps:
• Initialize an empty result list to store operations.
• Iterate through the integers in the range [1, n].
• For each integer, check if it matches the next expected element in `target`.
• If it matches, perform a 'Push' operation and move to the next target element.
• If it does not match, perform a 'Push' followed by a 'Pop' to discard the integer.
• Stop processing once all elements of `target` are matched.
Empty Inputs:
• Input: target = [], n = 5 -> Output: []
Large Inputs:
• Input: target = [1, 2, ..., 100], n = 100 -> Operations would be ['Push'] repeated 100 times.
Special Values:
• Input: target = [1], n = 1 -> Output: ["Push"]
Constraints:
• target must be strictly increasing.
vector<string> buildArray(vector<int>& target, int n) {
vector<string> ans;
int currElem=1;
for(int i=0;i<target.size();i++){
while(currElem!=target[i]){
ans.push_back("Push");
ans.push_back("Pop");
currElem++;
}
ans.push_back("Push");
currElem++;
}
return ans;
}
1 : Function Definition
vector<string> buildArray(vector<int>& target, int n) {
Defines the function `buildArray`, which takes a vector `target` (the target array to match) and an integer `n` (the upper limit for the array) as input. It returns a vector of strings representing the operations ('Push' and 'Pop') required to form the target array.
2 : Variable Initialization
vector<string> ans;
Initializes an empty vector `ans` to store the sequence of operations ('Push' and 'Pop') that will form the target array.
3 : Variable Initialization
int currElem=1;
Initializes the variable `currElem` to 1, which represents the current element being processed in the stack-based approach.
4 : Loop
for(int i=0;i<target.size();i++){
Starts a loop to iterate through each element in the `target` array. The goal is to simulate the stack operations to match each element in the target array.
5 : Condition Check
while(currElem!=target[i]){
Checks if the current element (`currElem`) is not equal to the current target element (`target[i]`). If they are not equal, additional 'Push' and 'Pop' operations are needed.
6 : Push Operation
ans.push_back("Push");
Adds a 'Push' operation to the result vector `ans`, simulating pushing the current element (`currElem`) onto the stack.
7 : Pop Operation
ans.push_back("Pop");
Adds a 'Pop' operation to the result vector `ans`, simulating popping the element off the stack after it has been pushed.
8 : Increment
currElem++;
Increments `currElem` to represent the next element to be processed in the stack-based approach.
9 : Push Operation
ans.push_back("Push");
Adds a final 'Push' operation to the result vector `ans` to push the current target element onto the stack.
10 : Increment
currElem++;
Increments `currElem` to represent the next element after pushing the current target element.
11 : Return Statement
return ans;
Returns the result vector `ans`, which contains the sequence of operations ('Push' and 'Pop') needed to build the target array.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each integer from the stream is processed exactly once, leading to a linear time complexity.
Best Case: O(1)
Worst Case: O(1)
Description: No additional data structures are used beyond the result list.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus