Nearest smaller to left

Problem

In case of this problem, an array is given and we have to find first smaller element to the left of current element. Similalrly, find the smaller elements for each element in the array and if greater element is not available then return a default value based on the problem.

Example -

Input: [1, 3, 0, 2, 5]
Output: [-1, 1, -1, 0, 2]

Input: [1, 6, 4, 10, 2, 5]
Output: [-1, 1, 1, 4, 1, 2]

Few points to consider:

1. If the array is sorted in decreasing order then next smaller element to left will always be -1.
2. For the left most element, left smaller element will always be -1.

We will see two ways to solve the problems

1. Brute-force approach (using nested loops)
2. Using stack

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.

def nearest_smaller_to_left(arr):
    result = []
    for i in range(0, len(arr)):
        for j in range(i-1, -1, -1):
            if arr[i] > arr[j]:
                result.append(arr[j])
                break
        else:
            result.append(-1)

    return result

arr = [6, 4, 10, 2, 5]
print(nearest_smaller_to_left(arr))

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

  return result;
}

arr = [6, 4, 10, 2, 5];
console.log(nearestSmallerToLeft(arr));

Output

[-1, -1, 4, -1, 2]

Although, we have solved this problem using loops but this is not an optimized solution. Because time complexity of this solution is O(n^2).

Using stack

Algorithm

NearestSmallerToRight(A)
1. for i = 0 to A.length
2.   if stack is empty
3.     result.add(-1)
4.     stack.push(A[i])
5.   else if stack is not empty
6.     while (stack is not empty AND A[i] < top of stack)
7.       stack.pop()
8.     if stack is empty
9.       result.add(-1)
10.    else
11.      result.add(top of stack)
12.    stack.push(A[i])
13. return result

In this approach, we are using a stack.

We have 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.

If the stack is empty the smaller element to left will be -1 otherwise top of stack will be the smaller element. At the end we have to return result array.

Initially, input array will be given and an output array with stack will be created.

Start traversing of array from the left side and for the leftmost element nearest smaller to left will be -1 and put the value from the input array into the stack for further comparision.

For 4, stack is not empty so we have to check the top most value if it is smaller than 4 or not. Here we observe that 6 (top of stack) is not smaller than 4 so pop off 6 from stack and now stack is empty so -1 will be inserted into output array and 4 will be pushed into the stack.

For 10, stack is not empty so check the top of stack and the top of stack i.e., 4 is smaller than 10 so add 4 in the output array and push 10 into the stack.

For 2, the top of stack is 10 which is not smaller than 2 so pop off 10 and then the top of stack is 4 which is also not smaller than 2 so pop off 2 also. Now, stack is empty so add -1 into the output array and push 2 into the stack for further comparision.

For 5, the top of stack is 2 which is obviously smaller than 5 so insert 2 into the output array and push 5 into the stack.

At the end, return the result array to get final result.

Program

class Stack:
    def __init__(self):
        self.stack = []

    def isEmpty(self):
        return len(self.stack) == 0

    def push(self, num):
        self.stack.append(num)

    def pop(self):
        if self.isEmpty():
            raise Exception('Stack Underflow')
        return self.stack.pop()

    def peek(self):
        if self.isEmpty():
            return None
        return self.stack[-1]

def nearestSmallerToLeft(arr):
    stack = Stack()
    result = []

    for i in range(0, len(arr)):
        if stack.isEmpty():
            result.append(-1)
            stack.push(arr[i])
        elif not stack.isEmpty():
            while(not stack.isEmpty() and arr[i] < stack.peek()):
                stack.pop()
            if stack.isEmpty():
                result.append(-1)
            else:
                result.append(stack.peek())
            stack.push(arr[i])
        
    return result

arr = [6, 4, 10, 2, 5]
print(nearestSmallerToLeft(arr))

class Stack {
    constructor() {
        this.stack = [];
    }
    
    isEmpty() {
        return this.stack.length === 0;
    }
    
    push(num) {
        this.stack.push(num);
    }
    
    pop() {
        if (this.isEmpty())
            throw 'Stack Underflow';
        return this.stack.pop();
    }
    
    peek() {
        if (this.isEmpty())
            throw null;
        return this.stack[this.stack.length-1]
    }
}

function nearestSmallerToLeft(arr) {
    const stack = new Stack();
    result = [];
    
    for (let i = 0; i < arr.length; i++) {
        if (stack.isEmpty()) {
            result.push(-1);
            stack.push(arr[i]);
        }
        else if (!stack.isEmpty()) {
            while (!stack.isEmpty() && arr[i] < stack.peek()) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                result.push(-1);
            } else {
                result.push(stack.peek());
            }
            stack.push(arr[i]);
        }
    }
    return result;
}

const arr = [6, 4, 10, 2, 5];
console.log(nearestSmallerToLeft(arr));

Output

[-1, -1, 4, -1, 2]