Stacks & QueuesProblem 38 of 38
Next Smaller Element
Problem Statement
Given an array of integers, find 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 with no smaller element on the right, consider NSE as -1.
Example:
Input: arr = [4, 8, 5, 2, 25]
For 4: Next smaller on right is 2 → NSE = 2
For 8: Next smaller on right is 5 → NSE = 5
For 5: Next smaller on right is 2 → NSE = 2
For 2: No smaller element on right → NSE = -1
For 25: No smaller element on right → NSE = -1
Output: [2, 5, 2, -1, -1]
Approach 1: Brute Force
Intuition
For each element, scan all elements to its right and find the first element that is smaller. This is straightforward but inefficient.
Algorithm
- For each element at index i:
- Scan from i+1 to end
- Find first element smaller than arr[i]
- If found, that's the NSE; otherwise, NSE = -1
java
import java.util.*;
public class NextSmaller {
public static int[] nextSmallerBruteForce(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[i]) {
result[i] = arr[j];
break;
}
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {4, 8, 5, 2, 25};
int[] result = nextSmallerBruteForce(arr);
System.out.print("Next Smaller Elements: ");
for (int x : result) System.out.print(x + " ");
System.out.println(); // 2 5 2 -1 -1
}
}Complexity Analysis
- Time Complexity: O(n^2) - nested loops
- Space Complexity: O(n) - for result array
Approach 2: Optimal (Using Stack)
Intuition
Use a monotonic stack that maintains elements in increasing order (from bottom to top). When we encounter an element smaller than the stack top, we've found the NSE for the stack top element. Process from right to left.
Algorithm
- Initialize result array with -1
- Traverse array from right to left
- For each element:
- Pop elements from stack while stack top >= current element
- If stack is not empty, stack top is the NSE
- Push current element to stack
java
import java.util.*;
public class NextSmaller {
public static int[] nextSmaller(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stk = new Stack<>();
// Traverse from right to left
for (int i = n - 1; i >= 0; i--) {
// Pop elements >= current
while (!stk.isEmpty() && stk.peek() >= arr[i]) {
stk.pop();
}
// If stack not empty, top is NSE
if (!stk.isEmpty()) {
result[i] = stk.peek();
}
// Push current element
stk.push(arr[i]);
}
return result;
}
public static void main(String[] args) {
int[] arr = {4, 8, 5, 2, 25};
int[] result = nextSmaller(arr);
System.out.print("Next Smaller Elements: ");
for (int x : result) System.out.print(x + " ");
System.out.println(); // 2 5 2 -1 -1
}
}Complexity Analysis
- Time Complexity: O(n) - each element pushed and popped at most once
- Space Complexity: O(n) - stack can hold up to n elements
Approach 3: Alternative (Left to Right with Indices)
Intuition
Process left to right. Use stack to store indices of elements waiting for their NSE. When current element is smaller than stack top, current element is NSE for stack top.
Algorithm
- Use stack to store indices
- For each element (left to right):
- While stack top element > current: pop and set result
- Push current index
- Remaining elements in stack have NSE = -1
java
import java.util.*;
public class NextSmaller {
public static int[] nextSmallerLeftToRight(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stk = new Stack<>(); // Store indices
for (int i = 0; i < n; i++) {
// Current element is NSE for all greater elements in stack
while (!stk.isEmpty() && arr[stk.peek()] > arr[i]) {
result[stk.pop()] = arr[i];
}
stk.push(i);
}
return result;
}
public static void main(String[] args) {
int[] arr = {4, 8, 5, 2, 25};
int[] result = nextSmallerLeftToRight(arr);
System.out.print("Next Smaller Elements: ");
for (int x : result) System.out.print(x + " ");
System.out.println(); // 2 5 2 -1 -1
}
}Complexity Analysis
- Time Complexity: O(n) - each element pushed and popped at most once
- Space Complexity: O(n) - stack space
Related Problems
Previous Smaller Element (PSE)
Next Greater Element (NGE)
Visual Walkthrough
Array: [4, 8, 5, 2, 25]
Processing right to left:
i=4 (25): Stack=[], push 25
Stack=[25], Result[4]=-1
i=3 (2): Stack=[25], 25>=2? No
Stack=[25], Result[3]=-1... wait
Actually 25>2, so we don't pop
Stack top=25 > 2, but we want smaller
Pop until stack top < current
Stack=[25], 25>=2? Yes, pop
Stack=[], Result[3]=-1
push 2, Stack=[2]
i=2 (5): Stack=[2], 2>=5? No
Result[2]=2
push 5, Stack=[2,5]
i=1 (8): Stack=[2,5], 5>=8? No
Result[1]=5
push 8, Stack=[2,5,8]
i=0 (4): Stack=[2,5,8], 8>=4? Yes, pop → [2,5]
5>=4? Yes, pop → [2]
2>=4? No
Result[0]=2
push 4, Stack=[2,4]
Final Result: [2, 5, 2, -1, -1]
Key Takeaways
- Monotonic Stack: Key technique for next/previous smaller/greater element problems
- Right to Left: Process from right when finding "next" element
- Left to Right: Process from left when finding "previous" element
- Stack Invariant: Maintain increasing stack for smaller, decreasing for greater
- O(n) Complexity: Each element pushed and popped at most once
- Related Problems: Stock Span, Largest Rectangle in Histogram, Trapping Rain Water