Build an Array With Stack Operations Leetcode Solution

The Build an Array With Stack Operations Leetcode Solution problem provides us with an integer sequence and an integer n. The problem states that we are given a sequence of integers from 1 to n. Then we use a stack to produce an integer sequence that is given to us as input. We can only use “Push” and “Pop” operations to obtain the given sequence. So, let us see a few examples before moving ahead with the solution.

target = [1,3], n = 3

["Push","Push","Pop","Push"]

Explanation: The operations given in the output can be verified on the sequence from 1 to n (=3). First, we push the first integer(=1) to the stack. Then since we can not ignore the integer (=2), we first push it into the stack, then pop it. Because the integer 2 is not in the output sequence. In the end, we push the third integer (=3) into the stack. Thus the required output is obtained.

target = [1,2,3], n = 3

["Push","Push","Push"]

Explanation: Since we have all the integers from the given sequence of 1 to n in the stack. We push all the integers into the stack. Thus we have 3 “Push” operations as output.

Approach for Build an Array With Stack Operations Leetcode Solution

The problem Build an Array With Stack Operations Leetcode Solution, as previously stated asked us to output the operations that a stack should act upon to produce the required output. The question is purely ad-hoc. And requires us to formulate an algorithm that can somehow find the stack operations.

For solving the problem, we create a variable “should_ve” that is initialized with 1. Then we proceed with a for loop that starts from 1 and stimulates the process of traversing over the sequence from 1 to n. We keep the variable should_ve to keep track of Push and Pop operations for the elements that do not find their place in the output sequence. So, to summarise the algorithm, we push each element but simply pop the elements that we don’t need.

Code for Build an Array With Stack Operations Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

vector<string> buildArray(vector<int>& target, int n) {
    vector<string> output;
    int should_ve = 1;
    for(int i=1;i<=target.size();i++){
        if(target[i-1] != should_ve){
            int cnt = target[i-1]-should_ve;
            while(cnt--)
                output.push_back("Push"), output.push_back("Pop");
        }
        output.push_back("Push");
        should_ve = target[i-1] + 1;
    }

    return output;
}

int main(){
    vector<int> target = {1, 3};
    int n = 3;
    vector<string> output = buildArray(target, n);
    for(auto x: output)
        cout<<x<<" ";
}

Push Push Pop Push

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> buildArray(int[] target, int n) {
        List<String> output = new ArrayList<String>();
        int should_ve = 1;
        for(int i=1;i<=target.length;i++){
            if(target[i-1] != should_ve){
                int cnt = target[i-1] - should_ve;
                while(cnt-- > 0){
                    output.add("Push");
                    output.add("Pop");
                }
            }
            output.add("Push");
            should_ve = target[i-1] + 1;
        }
        
        return output;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] target = {1, 3};
    int n = 3;
    List<String> output = buildArray(target, n);
    for(String x: output)
      System.out.print(x+" ");
  }
}

Push Push Pop Push

Complexity Analysis

Time Complexity

O(N), since we traverse over each of the elements from 1 to n. Thus the time complexity is linear.

Space Complexity

O(N), because we need to use an intermediate vector/array to store the output.