Monotonic Stack Patterns in Java: Efficient Algorithm Design

Monotonic stack patterns represent a powerful algorithmic approach for solving problems involving comparisons and ordering relationships in arrays and sequences, particularly effective for finding next greater elements, maximum subarrays, and optimizing stack-based computations.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the input array will contain at least one element, or should we handle empty arrays?
2. Do duplicate values in the input array need special handling, or can we treat them as equivalent?
3. Should the solution return indices or actual values from the input array?
4. Can we modify the input array in-place, or must we preserve it?
5. What is the expected time complexity for follow-up optimizations (e.g., O(n) vs O(n log n))?

Restatement of the pattern: The monotonic stack pattern is used to efficiently solve problems involving comparisons between elements in a sequence, particularly when we need to find the "next greater element" or similar relative ordering properties. It leverages a stack that maintains elements in either increasing or decreasing order to process elements from left to right and determine relationships between current and previous elements.

Signal words and constraint shape:

• "Next greater element" or "next smaller element"
• "Stack-based" or "monotonic property" requirements
• Problems involving relative ordering between elements in a sequence
• Need for efficient element comparison without nested loops

Assumptions made:

• The input is a linear sequence (array or list) of comparable elements
• We're typically looking for relative ordering relationships between adjacent or future elements
• The stack maintains a specific monotonic property (either increasing or decreasing)
• Elements are processed sequentially from left to right

Scenario suitability: This pattern is best suited for static scenarios where the entire input sequence is available upfront, as it requires processing all elements in a specific order to build and maintain the monotonic property. It's less naturally suited for streaming or online processing where elements arrive one at a time and we must maintain the monotonic invariant across all previously seen elements.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Next greater element" or "next smaller element"
• "Find the first element to the right that is larger/smaller"
• "Stack-based" or "monotonic" constraints
• Problems involving relative ordering or sequential relationships between elements
• When you need to process elements in order but want to efficiently find related elements

Why this pattern fits better than the most common alternatives:

• Unlike brute force O(n²) nested loops, monotonic stacks provide O(n) linear time complexity
• Compared to sorting-based approaches, monotonic stacks preserve original order and process elements sequentially
• Unlike hash maps for lookups, monotonic stacks naturally handle sequential dependencies without additional space overhead for storing indices

Conditions where a variation or related pattern applies instead:

• When you need to find elements that are not just the next one but any future element meeting criteria → use sliding window or two-pointer approaches
• When elements can be processed in any order → sorting or heap-based approaches might be more appropriate
• When you're looking for local maxima/minima in a continuous function → calculus or binary search approaches could work

The core insight that makes this pattern work: Elements are processed once and only when we know they can no longer be relevant for future comparisons. By maintaining a stack that preserves monotonicity (either increasing or decreasing), we can efficiently answer "what's the next element that satisfies my constraint?" in amortized O(1) time per element.

This pattern is particularly effective when:

• You're looking for relative ordering between adjacent elements in a sequence
• The problem has a "look ahead" component where future elements affect current processing
• You want to avoid nested loops while maintaining linear time complexity

3. Approach Evolution

Interview communication script:

My first instinct is to solve this with a brute force approach where I check for each element whether there's a greater element to its right by scanning the entire array — that would be O(n²) time because for each element, I'm doing a linear scan. But that's inefficient and not scalable.

Let me think about how to optimize this — I notice that if I maintain a stack of elements in increasing order, I can avoid re-scanning previously processed elements. When I encounter a new element that's larger than the top of stack, it becomes the "next greater element" for all elements in the stack that are smaller than this new element.

I notice that if I maintain a monotonic increasing stack (from bottom to top), and process elements from left to right, whenever I find an element that's larger than the stack top, it means this element is the next greater element for all elements in the stack that are smaller than it. This way, I can process each element only once and achieve O(n) time complexity.

The key insight is that elements in the stack are always in increasing order, and I can pop from the stack as soon as I find a greater element to assign it as the next greater element.

Brute-force approach and why it is not ideal:

The brute force approach would involve checking for each element whether there's a greater element to its right by scanning the entire array. For every element at index i, we iterate from i+1 to end of array to find the first element greater than nums[i]. This results in O(n²) time complexity because for each element, we potentially scan all remaining elements.

Improved approach and the key optimization:

The key optimization is to use a monotonic stack to maintain elements in increasing order. When we encounter an element that's larger than the top of the stack, it means this element is the next greater element for all elements in the stack that are smaller than it. We can pop these elements and assign their next greater element in one operation.

Final approach with step-by-step reasoning:

1. Use a stack to maintain elements in increasing order (monotonic stack)
2. Process array from left to right
3. For each element:
   • While stack is not empty and current element > stack top, pop and assign next greater element
   • Push current element to stack
4. Elements remaining in stack have no next greater element (assign -1)

Important invariants that must hold:

• Stack always maintains elements in increasing order from bottom to top
• Each element is pushed and popped at most once, ensuring O(n) time complexity
• Elements in stack are always elements that haven't found their next greater element yet

4. Data Structure Choice

The primary data structure for monotonic stack problems is a Stack (specifically ArrayDeque in Java for optimal performance).

Why Stack is Needed

The stack serves as the core mechanism to maintain the monotonic property (either increasing or decreasing order) while efficiently tracking elements that may need to be processed later. It allows us to:

• Push elements when they maintain the monotonic invariant
• Pop elements when a new element breaks the invariant but we can process the popped elements
• Access the most recent element in O(1) time for comparison operations

Time and Space Impact

Stack Operations:

• Push: O(1) amortized
• Pop: O(1) amortized
• Peek: O(1)
• Space: O(n) in worst case (when all elements are pushed and never popped)

ArrayDeque vs Stack: We prefer ArrayDeque over the legacy Stack class because:

• ArrayDeque has better performance characteristics (O(1) operations vs O(n) for stack's synchronized methods)
• It doesn't have the overhead of synchronization
• It's more memory efficient for typical stack usage patterns

Helper Structures

In some variants, we may use:

• HashMap: To store indices or counts for elements (e.g., when tracking next greater element by index)
• Array: For direct indexing when we know the input size and constraints (e.g., for bounded integer ranges)

The stack alone is sufficient for most monotonic stack problems, but the choice of additional structures depends on what information needs to be tracked beyond just element ordering.

The key insight is that the stack's monotonic property allows us to process elements in one pass while maintaining the necessary state for future comparisons.

5. Algorithm Walkthrough

Let's trace through the algorithm using the example prices = [10, 8, 5, 7, 4, 6, 3] to find the maximum profit with at most one transaction.

Step 1: Initialize minPrice = Integer.MAX_VALUE and maxProfit = 0.

Step 2: Process each price in order:

• Price = 10: minPrice = min(Integer.MAX_VALUE, 10) = 10, maxProfit = max(0, 10 - 10) = 0
• Price = 8: minPrice = min(10, 8) = 8, maxProfit = max(0, 8 - 8) = 0
• Price = 5: minPrice = min(8, 5) = 5, maxProfit = max(0, 5 - 5) = 0
• Price = 7: minPrice = min(5, 7) = 5, maxProfit = max(0, 7 - 5) = 2
• Price = 4: minPrice = min(5, 4) = 4, maxProfit = max(2, 4 - 4) = 2
• Price = 6: minPrice = min(4, 6) = 4, maxProfit = max(2, 6 - 4) = 2
• Price = 3: minPrice = min(4, 3) = 3, maxProfit = max(2, 3 - 3) = 2

Step 3: Return maxProfit = 2, which corresponds to buying at price 5 and selling at price 7.

Key insights during trace:

• We maintain minPrice as the lowest price seen so far (best buying opportunity)
• For each new price, we calculate potential profit by selling at that price
• The maximum profit is updated only when we find a better opportunity
• Edge case handling: If prices are strictly decreasing, maxProfit remains 0, which is correct

The algorithm correctly identifies that the optimal transaction is buying at price 5 and selling at price 7, yielding a profit of 2. The invariant that minPrice always represents the minimum price in the prefix ensures correctness of the solution.

6. Java Solution

import java.util.*;

public class MonotonicStackSolution {
    
    /**
     * Returns the next greater element for each element in the array.
     * For each element, finds the first greater element to its right.
     * Uses a monotonic decreasing stack to achieve O(n) time complexity.
     */
    public int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // Default value for elements with no greater element
        
        Stack<Integer> stack = new Stack<>(); // Stores indices of elements
        
        // Process elements from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Pop elements from stack that are smaller than current element
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            
            // If stack is not empty, top element is the next greater element
            if (!stack.isEmpty()) {
                result[i] = nums[stack.peek()];
            }
            
            // Push current index to stack
            stack.push(i);
        }
        
        return result;
    }
    
    /**
     * Returns the next greater element for each element in a circular array.
     * Handles circular nature by traversing the array twice.
     */
    public int[] nextGreaterElementCircular(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        
        Stack<Integer> stack = new Stack<>();
        
        // Traverse twice to handle circular nature
        for (int i = 2 * n - 1; i >= 0; i--) {
            int currentIndex = i % n;
            
            // Pop elements that are smaller than current
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[currentIndex]) {
                stack.pop();
            }
            
            // Only update result for first pass (i < n)
            if (i < n) {
                result[currentIndex] = stack.isEmpty() ? -1 : nums[stack.peek()];
            }
            
            stack.push(currentIndex);
        }
        
        return result;
    }
    
    /**
     * Returns the largest rectangle in a histogram.
     * Uses monotonic increasing stack to track heights.
     */
    public int largestRectangleInHistogram(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        
        // Add sentinel values to handle edge cases
        int[] extendedHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, extendedHeights, 1, heights.length);
        
        for (int i = 0; i < extendedHeights.length; i++) {
            // While stack is not empty and current height is less than stack top
            while (!stack.isEmpty() && extendedHeights[i] < extendedHeights[stack.peek()]) {
                int height = extendedHeights[stack.pop()];
                int width = i - stack.peek() - 1; // Width is between previous and current position
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

The solution implements three key monotonic stack problems:

1. Next Greater Element - O(n) time, O(n) space
2. Circular Next Greater Element - O(n) time, O(n) space
3. Largest Rectangle in Histogram - O(n) time, O(n) space

Each implementation uses a stack to maintain elements in specific order (decreasing or increasing) and processes elements in a single pass. The stack stores indices to efficiently calculate distances and areas.

7. Complexity Analysis

Time Complexity: O(n)

Each element is pushed and popped from the stack at most once, giving us a linear amortized time complexity. The key insight is that while we have nested loops in the code, the total number of operations across all iterations remains linear.

Space Complexity: O(n)

In the worst case, when the input array is strictly increasing, all elements will be stored in the stack before being processed. This results in O(n) space usage for the stack and O(n) for the result array, leading to an overall space complexity of O(n).

Why These Bounds Are Correct

The time analysis relies on the amortized cost argument: although we have a while loop inside the for loop, each element is processed exactly twice (once when pushed to stack, once when popped), making it O(2n) = O(n). The space complexity is straightforward as we store at most n elements in the stack and result array.

Optimality

This solution is optimal for this problem as we must examine each element at least once to determine the next greater element, making O(n) time complexity unavoidable. The solution achieves both optimal time and space complexity for the monotonic stack approach to this classic problem.

// Example of how we can verify O(n) time complexity:
// For array [1,2,3,4,5], each element is pushed once and popped once
// For array [5,4,3,2,1], each element is pushed once and popped once  
// The total operations remain linear regardless of input pattern

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return empty result (no elements to process)
• Single element: Monotonic stack will be empty after processing, but result should contain that element
• Two elements: Need to handle both increasing and decreasing cases properly

Duplicate Values and Repeated States

• Consecutive duplicates: When elements are equal, the monotonic property depends on whether we use strict inequality (<) or non-strict (<=)
• Multiple equal elements: May cause incorrect removal from stack if not handled carefully in the while loop condition
• Stack maintains uniqueness: When duplicates exist, we may need to track indices or use different comparison logic

Boundary Conditions

• All elements in increasing order: Stack will grow to full size, no removals occur
• All elements in decreasing order: Stack will be emptied after each element is processed
• Large input size: Stack operations must remain efficient (O(1) amortized push/pop)
• Integer overflow: When working with indices or large values, ensure proper bounds checking

Common Implementation Mistakes

• Incorrect while loop condition: Using stack.peek() < nums[i] instead of stack.isEmpty() || stack.peek() < nums[i] can cause IndexOutOfBoundsException
• Missing boundary checks: Not checking if stack is empty before calling stack.peek()
• Wrong return type handling: Assuming result array has same size as input when it might not (e.g., next greater element)
• Off-by-one errors in index handling: Misaligning array indices with stack operations
• Not maintaining proper monotonicity: Using wrong comparison operator (> vs <) breaks the stack's invariant

Implementation Specifics

• Stack initialization: Ensure stack is properly initialized as empty before processing begins
• Result array size: For problems like "Next Greater Element", result array should be same size as input, but for "Daily Temperatures" we might need to handle differently
• Index vs value confusion: When tracking indices, ensure the comparison logic aligns with whether we're comparing values or indices

9. Alternative Approaches

There are several alternative approaches to solving problems that might be solved with monotonic stacks, each with different trade-offs:

Brute Force with Nested Loops: For problems like Next Greater Element, we could check every element against every subsequent element. This approach has O(n²) time complexity and is inefficient for large inputs, but it's conceptually simple to understand and implement.

HashMap-Based Approach: Some problems can be solved by precomputing values using HashMaps to store element-to-index mappings. This works well for problems where we need to look up elements multiple times, but it requires O(n) extra space and doesn't leverage the ordered nature of the input.

Two-Pointer Technique: For certain array problems, a two-pointer approach might work, particularly when we're looking for pairs or ranges with specific properties. However, this is less applicable to monotonic stack problems where we're primarily concerned with element ordering and relative positioning.

Sorting-Based Approach: For some problems, sorting the array first might simplify the solution, but this destroys the original order and is only useful when we don't need to preserve the input sequence.

Binary Search Trees: For maintaining sorted order, a balanced BST could be used, but it introduces O(log n) insertion and lookup times, which is less efficient than the O(1) amortized operations provided by a monotonic stack.

The monotonic stack approach is preferred because it provides optimal O(n) time complexity with clean, intuitive logic that naturally handles the ordering constraints in these types of problems. The stack maintains a specific property (monotonicity) that makes it particularly well-suited for problems involving relative ordering of elements.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic increasing sequence
        int[] nums1 = {1, 2, 1, 3, 0};
        int[] expected1 = {2, 3, 3, -1, -1};
        // Expected: [2, 3, 3, -1, -1]
        
        // Test case 2: Decreasing sequence
        int[] nums2 = {5, 4, 3, 2, 1};
        int[] expected2 = {-1, -1, -1, -1, -1};
        // Expected: [-1, -1, -1, -1, -1]
        
        // Test case 3: Duplicate values
        int[] nums3 = {1, 1, 1, 1};
        int[] expected3 = {-1, -1, -1, -1};
        // Expected: [-1, -1, -1, -1]
        
        // Test case 4: Mixed sequence with duplicates
        int[] nums4 = {1, 2, 1, 3, 1, 4};
        int[] expected4 = {2, 3, 3, 4, 4, -1};
        // Expected: [2, 3, 3, 4, 4, -1]
        
        // Test case 5: Empty array
        int[] nums5 = {};
        int[] expected5 = {};
        // Expected: []
        
        // Test case 6: Single element
        int[] nums6 = {5};
        int[] expected6 = {-1};
        // Expected: [-1]
        
        // Test case 7: All same elements
        int[] nums7 = {3, 3, 3, 3, 3};
        int[] expected7 = {-1, -1, -1, -1, -1};
        // Expected: [-1, -1, -1, -1, -1]
        
        // Test case 8: Complex pattern
        int[] nums8 = {3, 1, 4, 1, 5, 9, 2, 6};
        int[] expected8 = {4, 4, 5, 5, 9, -1, 6, -1};
        // Expected: [4, 4, 5, 5, 9, -1, 6, -1]
    }
}

Sample Test Cases:

Basic case: [1, 2, 1, 3, 0] → [2, 3, 3, -1, -1]

• For index 0 (value 1): next greater is 2 at index 1
• For index 1 (value 2): next greater is 3 at index 3
• For index 2 (value 1): next greater is 3 at index 3
• For index 3 (value 3): no greater element → -1
• For index 4 (value 0): no greater element → -1

Edge case: Empty array [] → []

• No elements to process

Duplicate values: [1, 1, 1, 1] → [-1, -1, -1, -1]

• All elements are equal, so no greater element exists

Complex case: [3, 1, 4, 1, 5, 9, 2, 6] → [4, 4, 5, 5, 9, -1, 6, -1]

• For index 0 (value 3): next greater is 4 at index 2
• For index 1 (value 1): next greater is 4 at index 2
• For index 2 (value 4): next greater is 5 at index 4
• For index 3 (value 1): next greater is 5 at index 4
• For index 4 (value 5): next greater is 9 at index 5
• For index 5 (value 9): no greater element → -1
• For index 6 (value 2): next greater is 6 at index 7
• For index 7 (value 6): no greater element → -1

11. Final Summary

The core idea is to leverage a monotonic stack to efficiently process elements in a sequence while maintaining a specific ordering property, enabling optimal solutions for problems like next greater element, largest rectangle in histogram, and daily temperatures. This approach works by using a stack that maintains either increasing or decreasing order of elements, allowing us to process each element only once and achieve linear time complexity. The key insight is that we can discard elements from the stack when we find a better candidate, ensuring that each element is pushed and popped at most once, making the solution both time and space optimal for the given problem constraints.