DEV Community

Cover image for Nearest Smaller Element on Left  of an Array 
Ditikrushna Giri
Ditikrushna Giri

Posted on

Nearest Smaller Element on Left of an Array 

In this post, we are going to explore a very common question on Stack. The questions are the following ;

  • Nearest Smaller Element on Left

Let's assume we have given an array/vector/list with some elements and our job is to figure out the nearest smaller element on the left side of the array.
For instance :

 

let list = [ 4 , 10 , 5 , 8 , 20 , 15 , 3 , 12]
result = [-1 , 4 , 4 , 5 , 8 , 8 , -1 , 3] 
Enter fullscreen mode Exit fullscreen mode

And the smaller element of right side of an array

let list = [4 , 10 , 5 , 8 , 20 , 15 , 3 , 12]
result = [3 , 5 , 3 , 3 , 3 , 15 , 3 , 12 ]
Enter fullscreen mode Exit fullscreen mode

We will see two ways to solve the problems :

  • Brute-force approach (using nested loops)

In this approach we will use two loops. Outer loop will iterate over all the array items and inner loop will iterate over all the next elements of currently pointed by outer loop. Inner loop will check, if any smaller element will be found then loop will be terminated and if smaller element is not found then -1 will be added as result.

function nearestSmallerToLeft(list) {
  let result = [];
  for (let indexOne = 0; indexOne < list.length; indexOne++) {
    let flag = false;
    for (let indexTwo = indexOne - 1; indexTwo > -1; indexTwo--) {
      if (arr[indexOne] > arr[indexTwo]) {
        result.push(arr[indexTwo]);
        flag = true;
        break;
      }
    }
    if (!flag) {
      result.push(-1);
    }
  }

  return result;
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity of the above solution would be O(n^2)
Space Complexity would be : O(1) as we are not using any extra space .

  • Using stack

In case of this approach, we are using a stack. and the approach would be to start traversing elements of the given array from the start i.e., leftmost element and we will be putting the smallest element in the stack and whenever we get another smaller element then pop the stack and push the new element. Basically, we will be using a stack to keep values available to the left side and which are the smaller ones.


class Stack {
    constructor(){
        this.stack = [] ;
    }

    isEmpty() {
        return this.stack.length === 0;
    }
    push(element){
        this.stack.push(element);
    }
    pop(){
        if(this.isEmpty()){
            throw 'Stack UnderFlow';
        }
        return this.stack.pop();
    }

    top(){
        if(this.isEmpty())
        throw null ;
        return this.stack[this.stack.length-1];
    }
}


function nearestSmallerToLeft(list){
    const stack = new Stack();
    let result = [];

    for(let index = 0 ; index < list.length ; index++){

        if(stack.isEmpty()){
            result.push(-1);
            stack.push(list[index]);
        }
        else if(!stack.isEmpty()){
            while(!stack.isEmpty() && list[index]<stack.top()){
                stack.pop();
            }

            if(stack.isEmpty()){
                result.push(-1);
            }else{
                result.push(stack.top());
            }
            stack.push(arr[index]);
        }
    }

    return result ;
}
Enter fullscreen mode Exit fullscreen mode

Time complexity of the above solution would be O(n) And the space complexity O(n) as we are using extra space for stack .

Top comments (0)