Recent Posts

Next smaller element to the right

Written by

studymite

Problem

Find the next smaller element to the right in an array.

Brute Force Approach

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

TC – O(N2)

Optimal Approach

We can use a stack to reduce the time complexity. We will use the stack to find the smaller element in right.

  • We will 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 smaller 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 smaller 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 greater than current element.
#include<bits/stdc++.h>
using namespace std;

void nextSmallerElementRight(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 = i+1; j < size; 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 = size-1; i &gt;= 0; i--){
	if(s.empty()){
      	s.push(vec[i]);
    	ans.push_back(-1);
    } else if(s.top() &lt; vec[i]){
        ans.push_back(s.top());
        s.push(vec[i]);
    }else{
    	while(!s.empty()){
        	if(s.top() &lt; 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};
nextSmallerElementRight(vec);
for(auto num:vec) cout<<num<<" ";
return 0;
}

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

SC – O(N)

Next smaller element to the right