Next Smaller Number to Right for each element of a list using Stack in Python

In this tutorial, we will return the list of the next smaller number to right for each element of a list in Python.

Problem Statement:

Given a list, find the next smaller number to right for every element of the list. The next will consider as the right side for every element of the list.

If the next smaller number does not exist for any element of the list, consider -1 as the nearest smaller number.

Return the list of nearest/next smaller numbers to right for every element of the list.

EXAMPLE:-

INPUT:-   [4,5,2,10,8]

OUTPUT:- [2,2,-1,8,-1]

EXPLANATION:-

Element          Next Smaller number to the right 

4                             [ Next smaller number than 4 on the right side is 2]

5                          2    [ Next smaller number than 5 on the right side is 2]

2                         -1    [There is no smaller number than 2 on the right side, so consider -1]

10                           [ Next smaller number than 10 on the right side is 8]

8                         -1    [There is no smaller number than 8 on the right side, so consider -1]

Approach(1):- USING BRUTE-FORCE TECHNIQUE

A simple approach for this problem is the Brute force technique. In the Brute force technique, we will search for the next/nearest smallest number for each element of the list such that the index of the next smallest number is greater than the index of the element. It means we will search on the right side of the list for the next/nearest smaller number.

But the time complexity is not linear in this case. The time complexity will be O(N^2) where N is the length of the list.

This approach is a basic approach and not so much efficient. So now we will use STACK Data Structure to make our approach more efficient

in terms of time.

Approach (2) :- USING STACK

In this approach, we will use Stack to find the next/nearest smaller number to the right for each element of the list. If the next smaller number is not present for any element of the list, we will consider -1 as the next/nearest smaller number.

In this approach, we will start our loop from the right end of the list. Since the element at the last index is at the rightest position of the list we will consider -1 as the next smaller number for this position of the element.

After each iteration of the loop, we will push the element in the stack and then in every next loop, we will use this stored element of the stack.

We will use some if-else conditions which will help us to find the next smaller element. Since we are starting from the right end of the list so we will get the reversed form of the desirable output list. So make sure to reverse the list at the end before returning to printing it.

This approach will be more efficient as compared to the above Brute force technique.

I am mentioning the comment for each line of code that will clear the concept of this approach. Try to dry run this approach, will help a lot to clarify all the conditions.

So now coming to the implementation of the code using Python:

def nextsmaller(l):
    NEXT_SMALLER=[]     # initialize the list which will return as output.
    
    stack = []          # initialize stack using list.
    for i in range(0,len(l)):
        
        h = len(l)-1-i;    # setting the h value as it will take element from the right end of the list.
        
        
        # this if condition will work for only the element which is at right end i.e at -1
        if(h == len(l)-1): 
            NEXT_SMALLER.append(-1)
            
            
        # In this elif condition it will check if top element of the stack is less than the h[l] then this will be 
        # the next smaller element for h[l] as the index or position of top element of the stack is right to h[l] 
        elif(len(stack)>0 and stack[-1] < l[h]):
            NEXT_SMALLER.append(stack[-1])
        
        #In this elif condition it will check if top element of the stack is greater than the h[l] then pop out the 
        #top element of the stack till top element of the stack is not less than h[l] and also length of stack>0.
        elif(len(stack)>0 and stack[-1] > l[h]):
            while(len(stack)>0 and stack[-1] > l[h]):
                stack.pop()
                
            # if len(stack) == 0 append -1 since no number is less than h[l] to right
            if(len(stack) == 0):
                NEXT_SMALLER.append(-1)
            
            # if top element of stack is less than h[l] 
            else:
                NEXT_SMALLER.append(stack[-1])
        # append every h[l] element to stack for next loop
        stack.append(l[h])
    # Reverse the list because we started from the right end of the list
    NEXT_SMALLER.reverse()
    return(NEXT_SMALLER)
print(nextsmaller([4,5,2,10,8]))

OUTPUT:

[2, 2, -1, 8, -1]

Do comment if you like this lesson and also do comment for any suggestions regarding this tutorial.

Also read: Using Stacks to solve Desert Crossing Problem in Python

Leave a Reply

Your email address will not be published. Required fields are marked *