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] 

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 ]

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;
}

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 ;
}

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