Recent Posts

Next Larger Element

Written by

studymite

Problem

Find the next larger element in an array.

Stack can be used when

  • Where arrays are used and brute force is O(N2).
  • Where the value of j is dependent on the value of i.

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 right.

  • Traverse the array from the end, 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.
  • Finally, reverse the ans vector.

 

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

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


stack &lt;int&gt; s;
vector&lt;int&gt; ans;
for(int i = size-1; i &gt;= 0; 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};
nextGreaterElement(vec);
for(auto num:vec) cout<<num<<" ";
return 0;
}

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

SC – O(N)

Next Larger Element