Next Smaller Element In An Array

This blog will discuss the famous interview problem: find the Next smaller element in an array that has been previously asked in companies like Amazon, Samsung, Zoho, Payu, etc.

Problem Statement: An array of elements is given. The task is to find the next smaller for each element in the array. If there is no smaller element to the right of the element, then return -1.

Example:

Input: 2 1 4 3
Output: 1 -1  3 -1

Explanation:

• 1 is the next smaller element after 2.
• There is no smaller element after 1, so -1 is printed.
• 3 is the next smaller element after 4.
• There is no smaller element after 3, so -1 is printed.

Recommended: Please try to solve the “ Next Smaller Element” on GFG first before moving on to the solution.

Now let’s see various approaches to find the next smaller element in an array.

Brute force approach

The outer loop traverses the array from left to right. The inner loop will compare the current element with all the elements to its right until it finds an element smaller (in the next smaller element function) than the current element. If no such element is present, -1 is printed.

Steps:

1. Traverse the array from left to right in the outer loop.
2. Initialize nextSmaller with -1.
3. In the inner loop, traverse the array through the elements at the right of the current element.
4. In the next smaller function: if any element smaller than the current element is present, the next smaller element is obtained.

Code:

Complexity Analysis:

• Time Complexity: O(n²) as two nested for loops are used.
• Space Complexity: O(1) as no extra space is required.

Where “n” is the size of the array.

Stack approach

In this approach, a monotonic stack is used. In this case, to find the next smaller element, an increasing monotonic stack is used.

In an increasing monotonic stack, the top element is removed if the element to be inserted is smaller than the top element. This procedure is repeated until the monotonic stack becomes empty or the top element is smaller than the item to be inserted.

Steps:

1. Initialize a stack and array.
2. Traverse the array from the end.
3. Update the monotonic stack as explained above.
4. Add the next smaller element in the array. If the stack is empty, i.e., no element is present, then add -1.
5. Add the current element to the stack.

Code:

Complexity Analysis:

• Time Complexity: O(n) as only a single traversal is required.
• Space Complexity: O(n) as extra space is required for the stack and array.

That’s it from my side, I hope you found this post useful 😊.

Let’s get connected on Github/LinkedIn/Website/Twitter/Quora ;)

And if you have any suggestions, feel free to get in touch with me over LinkedIn & the comment section is also all yours.

If you liked this story, hit the clap button as it motivates me to write more & better.