Next Smaller Element

 ven an array, print the Next Smaller Element (NSE) for every element. The NSE for an element x is the first smaller element on the right side of x in the array. For elements for which no smaller element exists (on the right side), then consider NSE as -1. 

Examples:

Input: [4, 8, 5, 2, 25]

Output: [2, 5, 2, -1, -1]

Explanation: 

The first element smaller than 4 having index > 0 is 2.

The first element smaller than 8 having index > 1 is 5.

The first element smaller than 5 having index > 2 is 2.

There are no elements smaller than 4 having index > 3.

There are no elements smaller than 4 having index > 4.

Input: [13, 7, 6, 12]

Output: [7, 6, -1, -1]

Explanation: 

The first element smaller than 13 having index > 0 is 7.

The first element smaller than 7 having index > 1 is 6.

There are no elements smaller than 6 having index > 2.

There are no elements smaller than 12 having index > 3. 

[Expected Approach] using Stack - O(n) Time O(n) Space

The idea is to find the next smaller element for each element in the list using a monotonic stack. We traverse the list while maintaining a stack that keeps indices of elements in decreasing order. If the current element is smaller than the element at the stack's top, it becomes the next smaller element for that index. We then update the result and pop the stack until this condition no longer holds. If no smaller element exists, we keep -1. 

Steps to implement the above idea:

Initialize a list next_smaller with -1 and an empty stack.

Iterate through the list while maintaining a monotonic decreasing stack (stores indices).

Check if the current element is smaller than the element at the stack's top.

Update next_smaller for popped indices and remove elements from the stack.

Push the current index onto the stack to maintain order.

Return the next_smaller list after completing the traversal.

Below is the implementation of the above approach:

import java.util.*;

class GfG {

    // Function to find the next smaller element for each element in the array

    static List<Integer> findNextSmallerElement(List<Integer> arr) {

        int n = arr.size();

        // Stores the next smaller elements, initialized with -1

        List<Integer> nextSmaller = new ArrayList<>(Collections.nCopies(n, -1));

        // Monotonic stack to keep track of indices

        Stack<Integer> stk = new Stack<>();

        // Iterate through the array

        for (int i = 0; i < n; i++) {

           

            // Maintain a decreasing order in the stack

            while (!stk.isEmpty() && arr.get(i) < arr.get(stk.peek())) {

                nextSmaller.set(stk.pop(), arr.get(i)); // Assign the next smaller element

            }

            // Push the current index onto the stack

            stk.push(i);

        }

        return nextSmaller;

    }

    // Driver function

    public static void main(String[] args) {

        // Input list

        List<Integer> arr = Arrays.asList(4, 8, 2, 1, 6, 10, 5);

        // Function call to find next smaller elements

        List<Integer> result = findNextSmallerElement(arr);

        // Print the original list

        System.out.println("Original List: " + arr);

        // Print the next smaller elements

        System.out.println("Next Smaller Elements: " + result);

    }

}