![Monotonic Stack Trick](/images/monotonic-stack-trick.png) # Monotonic Stacks: From O(n²) to O(n) ## Introduction When solving array problems involving finding the next greater element, next smaller element, or their previous counterparts, a naive approach using nested loops results in O(n²) time complexity. **Monotonic stacks** provide an elegant solution that reduces this to O(n). ## What is a Monotonic Stack? A **monotonic stack** is a stack that maintains elements in either strictly increasing or strictly decreasing order. The key insight is that we can use this ordered structure to efficiently find relationships between elements. ### Types of Monotonic Stacks 1. **Monotonic Decreasing Stack**: Elements decrease from bottom to top (smaller elements on top) - Used to find the **next greater element** 2. **Monotonic Increasing Stack**: Elements increase from bottom to top (larger elements on top) - Used to find the **next smaller element** ## The Classic Problem: Next Greater Element Given an array, find the next greater element for each element. If no greater element exists, return -1. **Example:** ``` Input: [4, 5, 2, 10, 8] Output: [5, 10, 10, -1, -1] ``` ### Naive Approach (O(n²)) ```java public int[] nextGreaterElement(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { result[i] = -1; for (int j = i + 1; j < n; j++) { if (nums[j] > nums[i]) { result[i] = nums[j]; break; } } } return result; } ``` ### Monotonic Stack Approach (O(n)) The key idea: use a **monotonic decreasing stack** that stores indices. As we iterate, if the current element is greater than the element at the top of the stack, we've found the next greater element for that index. ```java import java.util.*; public int[] nextGreaterElement(int[] nums) { int n = nums.length; int[] result = new int[n]; Arrays.fill(result, -1); Stack stack = new Stack<>(); // Stores indices for (int i = 0; i < n; i++) { // While current element is greater than element at top index while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { int index = stack.pop(); result[index] = nums[i]; // Found next greater element } stack.push(i); // Push current index } return result; } ``` ### How It Works Let's trace through the example `[4, 5, 2, 10, 8]`: 1. **i = 0, nums[0] = 4** - Stack: `[]` - Push index 0: `[0]` 2. **i = 1, nums[1] = 5** - Stack top: index 0, value 4 - 5 > 4 → Pop 0, set result[0] = 5 - Push index 1: `[1]` 3. **i = 2, nums[2] = 2** - Stack top: index 1, value 5 - 2 < 5 → No pop, push index 2: `[1, 2]` 4. **i = 3, nums[3] = 10** - Stack top: index 2, value 2 - 10 > 2 → Pop 2, set result[2] = 10 - Stack top: index 1, value 5 - 10 > 5 → Pop 1, set result[1] = 10 - Push index 3: `[3]` 5. **i = 4, nums[4] = 8** - Stack top: index 3, value 10 - 8 < 10 → No pop, push index 4: `[3, 4]` **Final result:** `[5, 10, 10, -1, -1]` ## Why Monotonic Decreasing Stack Works The stack maintains elements in decreasing order. When we encounter a larger element: - All smaller elements in the stack have found their "next greater element" - We can process them immediately - The current element becomes a candidate for future elements ## Common Variations ### 1. Next Smaller Element Use a **monotonic increasing stack**: ```java public int[] nextSmallerElement(int[] nums) { int n = nums.length; int[] result = new int[n]; Arrays.fill(result, -1); Stack stack = new Stack<>(); for (int i = 0; i < n; i++) { // While current element is smaller than element at top while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { int index = stack.pop(); result[index] = nums[i]; } stack.push(i); } return result; } ``` ### 2. Previous Greater Element Iterate from right to left with a decreasing stack: ```java public int[] previousGreaterElement(int[] nums) { int n = nums.length; int[] result = new int[n]; Arrays.fill(result, -1); Stack stack = new Stack<>(); for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { int index = stack.pop(); result[index] = nums[i]; } stack.push(i); } return result; } ``` ### 3. Previous Smaller Element Iterate from right to left with an increasing stack: ```java public int[] previousSmallerElement(int[] nums) { int n = nums.length; int[] result = new int[n]; Arrays.fill(result, -1); Stack stack = new Stack<>(); for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { int index = stack.pop(); result[index] = nums[i]; } stack.push(i); } return result; } ``` ## Real-World Applications Monotonic stacks are used in problems like: 1. **Largest Rectangle in Histogram** - Finding the largest rectangle that can be formed 2. **Trapping Rain Water** - Calculating trapped rainwater 3. **Daily Temperatures** - Finding days with warmer temperatures 4. **Remove K Digits** - Removing digits to form smallest number 5. **Next Greater Node in Linked List** - Finding next greater values ## Time Complexity Analysis - **Time Complexity**: O(n) - Each element is pushed and popped at most once - **Space Complexity**: O(n) - Stack can hold at most n elements ## Key Takeaways 1. **Monotonic Decreasing Stack** → Find next/previous **greater** element 2. **Monotonic Increasing Stack** → Find next/previous **smaller** element 3. **Direction matters**: Left-to-right finds "next", right-to-left finds "previous" 4. **Stack stores indices** (not values) for easy result array updates 5. **Each element processed once** → O(n) time complexity ## Practice Problems 1. [Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/) 2. [Daily Temperatures](https://leetcode.com/problems/daily-temperatures/) 3. [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/) 4. [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/) ## Conclusion Monotonic stacks are a powerful pattern for solving array problems efficiently. By maintaining elements in sorted order, we can process relationships between elements in linear time. Master this pattern, and you'll find it applicable to many competitive programming and interview problems!

Writing

Monotonic Stacks: From O(n²) to O(n)