Build An Array With Stack Operations - Leetcode Solution

Problem Statement:

Given an array target and an integer n. In each iteration, you will read a number from n and push it to the stack. Then, you will do the following operations until you reach the target array:

1. Pop the top element from the stack and add it to the result array.
2. If the popped element is equal to the current element in the target array, move to the next element in the target array.
3. If not, push the next element in the target array onto the stack and continue from step 1.

You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to n inclusive.

Return the operations to build the target array. You are guaranteed that the answer is unique.

Solution:

Approach: We can use a stack to simulate the process to build the target array. We iterate the target array and in each iteration, we try to push the next element in the target array onto the stack and pop the top elements from the stack until the top element is equal to the current element in the target array. We then move to the next element in the target array and repeat the process until we reach the end of the target array.

Code:

class Solution { public: vector<string> buildArray(vector<int>& target, int n) { vector<string> res; stack<int> st; int index = 0; for(int i = 1; i <= n; i++) { if(st.empty() || st.top() != target[index]) { st.push(i); res.push_back("Push"); } else { index++; } if(index == target.size()) break; } while(!st.empty()) { st.pop(); res.push_back("Pop"); } return res; } };

Explanation:

1. We initialize an empty stack and the index to 0 to keep track of the current element in the target array.
2. We iterate from 1 to n.
3. If the stack is empty or the top element of the stack is not equal to the current element in the target array, we push the current number onto the stack and add "Push" to the result vector.
4. If the top element in the stack is equal to the current element in the target array, we move to the next element in the target array by incrementing the index.
5. If we reach the end of the target array, we break out of the loop.
6. After the loop, we pop all the remaining elements from the stack and add "Pop" to the result vector.
7. Finally, we return the result vector.

Time Complexity: O(n) Space Complexity: O(n)

1