Recent Posts

Next greater to left

Written by

studymite

Problem

Find the next larger element to the left in an array.

Brute Force Approach

By using two nested for loops we can find the next larger element.

TC – O(N2)

Optimal Approach

We can use a stack to reduce the time complexity. We will use the stack to find the greater element in left.

  • Traverse the array from the start, if the stack is empty push -1 to ans vector and push the current value to the stack.
  • If the stack is not empty, check if the stack top is greater than the current value if yes then push stack top to ans array and the current value to stack.
  • Else pop the stack until tack top is greater than the current value, and if the stack is empty push -1 and current value to stack.
  • There will no need for elements that are popped because they are popped only because they are smaller than current element.


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

void nextGreaterElementLeft(vector<int> &vec){
int size = vec.size();
/* O(N^2)
vector<int> ans;
for(int i = 0; i < size; i++){
int flag = 0;
for(int j = 0; j < i; j++){
if(vec[j] > vec[i]){
ans.push_back(vec[j]);
flag = 1;
break;
}
}
if(flag == 0) ans.push_back(-1);
}
vec = ans;
*/


stack &lt;int&gt; s;
vector&lt;int&gt; ans;
for(int i = 0; i &lt; size; i++){
	if(s.empty()){
      	s.push(vec[i]);
    	ans.push_back(-1);
    } else if(s.top() &gt; vec[i]){
        ans.push_back(s.top());
        s.push(vec[i]);
    }else{
    	while(!s.empty()){
        	if(s.top() &gt; vec[i]){
              	ans.push_back(s.top());
        		s.push(vec[i]);
              	break;
            }
          	s.pop();
        }
      	if(s.empty()){
          	s.push(vec[i]);
        	ans.push_back(-1);
        }
    }
}
//reverse(ans.begin(), ans.end());
vec = ans;



}


int main() {
vector<int> vec = {1,3,2,4};
nextGreaterElementLeft(vec);
for(auto num:vec) cout<<num<<" ";
return 0;
}


TC – O(N) // stack push pop is O(1)


SC – O(N)


Next greater to left