Stack: Build an Array With Stack Operations

Problem Statement:

You are given an target and an integer n.
You need to perform push and pop operation to reach the target by using the list from “1, 2, … n”.

Example

Input: target = [1,3], n = 3
Output: [“Push”,”Push”,”Pop”,”Push”]

Read number 1 and do push operation. Current array [1]
Then read number 2 and do push and pop from the array. Current array [1]
Then read number 3 and push the array, current array [1,3]

Solution

We use array to solve this problem.

So for every value that is not present in the target, we do “push” and then “pop”.

If there is a matching value then do “push” opeeration.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

vector<string> build_array(vector<int>& target, int n) 
{
      vector<string> res;
      string ph = "Push";
      string pp = "Pop";
      int num = 1;
      for(int i=0; i<target.size(); i++) 
      {
          while(num!=target[i]) 
          {
              num++;
              res.push_back("Push");
              res.push_back("Pop");
          }
          res.push_back("Push");
          num++;
      }
      return res;
  }

int main()
{ 
    vector<int> target = {1, 3};
    int n = 3;

    vector<string> result = build_array(target, n);


    cout<<"Result is "<<endl;
    for (auto i = result.begin(); i != result.end(); ++i)
    cout << *i << " ";

    cout<<endl;

    return 0;

}

Output:

Result is
Push Push Pop Push
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *