Nearest Smaller to Right

Question

Write a program to find the nearest smaller element or next smaller element to the right of each element in an array.

Example -

Input: [40, 50, 20,10, 60]
Output: [20,20,10,-1,-1]

Input: [11, 6, 42, 65, 32, 54]
Output: [6, -1, 32, 32, -1, -1]

Note:-

1. If the array is sorted in increasing order, next smaller element will always be -1.
2. For the right most element, the right smaller element will always be -1.

 

Answer 1

We can solve this problem in two ways-

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

Method 1- Brute-force approach (using nested loops)-

In this method, two loops will be used. The outer loop will iterate over all the array elements and the inner loop will iterate over all the next elements of currently pointed by outer loop. The inner loop will be terminated if any smaller element will be found and if the greater element is not found then -1 will be added as result.

# Python program to print next smaller to right using Brute-force approach (using nested loops)

def nearest_smaller_to_right(arr):

  result = []

  for i in range(0, len(arr)):

    for j in range(i+1,len(arr)):

      if arr[i] > arr[j]:

        result.append(arr[j])

        break

    else:

      result.append(-1)

  return result

arr = [11, 6, 42, 65, 32, 54]

print(nearest_smaller_to_right(arr))

Output:

[6, -1, 32, 32, -1, -1]

Time Complexity: O(n^2). This is not an optimized solution.

Method 2- Using Stack-

# Python program to print next smaller to right element using stack

from collections import deque

#class to create stack and basic operations on stack

class Stack:

    def __init__(self):

        self.stack = deque()  #can take list also like self.stack=[]

    

    def push(self,data):

        self.stack.append(data)

        

    def pop(self):

        if self.is_empty():

          raise Exception('Stack Underflow')

        return self.stack.pop()

    

    def peek(self):

        if self.is_empty():

          return None

        return  self.stack[-1]

    

    def is_empty(self):

        return len(self.stack)==0

    

    def size(self):

        return len(self.stack)

#function to print next smaller to right element using stack

def nearest_smaller_to_right(arr):

  #making object of Stack class

  stack = Stack()

  result = []

  #start traversing from last element

  for i in range(len(arr)-1,-1,-1):

    if stack.is_empty():

      result.append(-1)

    # if stack is not empty

    elif not stack.is_empty():

      #then pop an element from stack if top of stack is smaller then arrayelement  

      while(not stack.is_empty() and arr[i] < stack.peek()):

        stack.pop()

      #while loop ends if one of 2 conditions true, if sack empty 

      #append -1 to result else append top of stack to result

      if stack.is_empty():

        result.append(-1)

      else:

        result.append(stack.peek())

    # push the processesd element to stack

    stack.push(arr[i])

  result.reverse()

  return result

arr = [11, 6, 42, 65, 32, 54]

print(nearest_smaller_to_right(arr))

Output: 

[6, -1, 32, 32, -1, -1]

Time Complexity: O(n)