44-Nearest-Smaller-Element.md

Nearest Smaller Element

Problem Link

Practice Problem

---

Pattern

• Stack
• Monotonic Stack

---

Approach

Use an increasing stack to find the nearest smaller element on the left for each array value.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int[] nearestSmallerToLeft(int[] nums) {
        int[] ans = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && stack.peek() >= nums[i]) stack.pop();
            ans[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return ans;
    }
}