Next Smaller Element

geeksforgeeks.org

Problem Statement

Given an array, find the first smaller element on the right for every element.

If no such element exists, return -1.

---

Brute Force Intuition

For every element:

Scan towards the right.

The first smaller element is the answer.

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int[] nextSmaller(int[] arr) {

        int n = arr.length;

        int[] ans = new int[n];

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

            ans[i] = -1;

            for (int j = i + 1; j < n; j++) {

                if (arr[j] < arr[i]) {

                    ans[i] = arr[j];
                    break;
                }
            }
        }

        return ans;
    }
}

---

Moving Towards the Optimal Approach

Instead of searching to the right every time:

Traverse from:

Right → Left

Maintain a stack containing only useful candidates.

---

Pattern Recognition

Whenever you see:

• Next Smaller
• Previous Smaller
• Next Greater
• Previous Greater

Think:

Monotonic Stack

---

Optimal Approach

For every element:

Remove all elements:

>= Current Element

If stack is empty:

Answer = -1

Else:

Answer = Stack Top

Push current element.

---

Optimal Java Solution

class Solution {

    public int[] nextSmaller(int[] arr) {

        int n = arr.length;

        int[] ans = new int[n];

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

        for (int i = n - 1; i >= 0; i--) {

            while (!st.isEmpty() &&
                   st.peek() >= arr[i]) {

                st.pop();
            }

            ans[i] = st.isEmpty()
                    ? -1
                    : st.peek();

            st.push(arr[i]);
        }

        return ans;
    }
}

---

Dry Run

arr = [4,8,5,2,25]

Process from right:

25 → -1

2 → -1

5 → 2

8 → 5

4 → 2

Answer:

[2,5,2,-1,-1]

---

Complexity Analysis

Metric	Complexity
Time	O(N)
Space	O(N)

---

Interview One-Liner

Traverse from right using a monotonic increasing stack so the top always represents the next smaller element.