🚀 Day 5: Mastering the Monotonic Stack & Queue Pattern (Amazon Interview Series)

The Monotonic Stack/Queue pattern helps solve problems where you need to find:

• Next Greater / Smaller Element
• Previous Greater / Smaller Element
• Stock Span / Temperature rise / Water trapping

Amazon loves this because it reduces O(n²) brute force into O(n) using a stack/queue that maintains a monotonic order (either increasing or decreasing).

---

🔑 Core Idea

• Use a stack to store indices or values.

• Maintain a monotonic order:

  • Increasing stack → find next smaller element.
  • Decreasing stack → find next greater element.

• Pop when order is violated → process that element.

---

📝 Problem 1: Next Greater Element I

👉 Amazon-style phrasing:
Given two arrays nums1 and nums2, for each element in nums1, find the next greater element in nums2.

Java Solution

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.getOrDefault(nums1[i], -1);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {4,1,2}, nums2 = {1,3,4,2};
        System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2))); 
        // Output: [-1, 3, -1]
    }
}

✅ Time Complexity: O(n)

---

📝 Problem 2: Daily Temperatures

👉 Amazon-style phrasing:
Given a list of daily temperatures, return a list such that each element is the number of days until a warmer temperature. If there is none, put 0.

Java Solution

import java.util.*;

public class DailyTemperatures {
    public static int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int prev = stack.pop();
                result[prev] = i - prev;
            }
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] temps = {73,74,75,71,69,72,76,73};
        System.out.println(Arrays.toString(dailyTemperatures(temps))); 
        // Output: [1,1,4,2,1,1,0,0]
    }
}

✅ Time Complexity: O(n)
✅ Why Amazon asks: This is disguised scheduling + stack.

---

📝 Problem 3: Trapping Rain Water

👉 Amazon-style phrasing:
Given elevation heights, compute how much rainwater can be trapped after raining.

Java Solution

public class TrappingRainWater {
    public static int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0;

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;

                int distance = i - stack.peek() - 1;
                int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
                water += distance * boundedHeight;
            }
            stack.push(i);
        }
        return water;
    }

    public static void main(String[] args) {
        int[] h = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(h)); // Output: 6
    }
}

✅ Time Complexity: O(n)
✅ Why Amazon asks: Looks like DP but stack is cleaner + efficient.

---

📝 Problem 4: Largest Rectangle in Histogram

👉 Amazon-style phrasing:
Given an array of heights, return the area of the largest rectangle in a histogram.

Java Solution

import java.util.*;

public class LargestRectangleHistogram {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;

        for (int i = 0; i <= heights.length; i++) {
            int h = (i == heights.length ? 0 : heights[i]);
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2,1,5,6,2,3};
        System.out.println(largestRectangleArea(heights)); // Output: 10
    }
}

✅ Why Amazon asks: AWS teams deal with load balancing, utilization peaks — this problem maps directly.

---

📝 Problem 5: Sliding Window Maximum (Monotonic Queue)

👉 Amazon-style phrasing:
Given an array and window size k, return the maximum of each sliding window.

Java Solution

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new LinkedList<>();
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int ri = 0;

        for (int i = 0; i < n; i++) {
            // Remove out of window
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();

            // Maintain decreasing deque
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();

            dq.offerLast(i);

            // Window ready
            if (i >= k - 1) result[ri++] = nums[dq.peekFirst()];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
        // Output: [3,3,5,5,6,7]
    }
}

✅ Time Complexity: O(n)
✅ Amazon focus: Queue optimization, fits into log/stream processing.

---

📚 Extended Problem List (Practice)

1. Stock Span Problem – Days stock price was <= today’s.
2. Next Greater Element II (Circular Array).
3. Remove K Digits – Remove k digits to form smallest number (monotonic stack trick).
4. Asteroid Collision – Resolve collisions using stack.
5. Minimum Remove to Make Valid Parentheses – Balanced parentheses with stack.

---

🎯 Key Takeaways

• Monotonic stack/queue = maintain order for O(n) scans.
• Essential for Amazon optimization + scheduling.
• Think of it as a “future knowledge pattern” → you’re finding next/previous optimal.

---

📅 Next in the series (Day 6):
👉 Binary Search on Answer Pattern – Koko Eating Bananas, Ship Packages in D Days, and Split Array Largest Sum (Amazon classics).

---