Next Smaller Element to Left in an array

Problem

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

Brute Force Approach

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

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

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

SC – O(N)