L5: Next Greater Element | Stack and Queue Playlist

This comprehensive study note explores the Next Greater Element (NGE) problem, marking the introduction of the Monotonic Stack pattern in data structures and algorithms. It covers problem identification, naive approaches, optimal backward traversal, the light-pole intuition, pseudocode implementation, and rigorous complexity analysis.

1. What is a Monotonic Stack?

A Monotonic Stack is a specialized stack data structure where elements are maintained in a specific sorted order (either strictly increasing, decreasing, non-increasing, or non-decreasing) throughout its operations.

• Key Characteristic: Whenever a new element is pushed, any elements violating the target order are popped from the stack.
• Primary Use Case: Efficiently finding the next greater, previous greater, next smaller, or previous smaller element in an array without resorting to nested loops.

Monotonic Decreasing Stack Structure:
Bottom [ 12, 6, 4, 2, 1 ] Top

2. Problem Statement: Next Greater Element (NGE)

Given an array of integers, for every element in the array, find the first greater element that appears to its right. If no such greater element exists on the right, assign -1 for that position. Finally, return the resulting array or list of next greater elements.

Example Walkthrough

• Input Array: [6, 0, 8, 1, 3]

• Step-by-Step NGE Resolution:

  • Standing at 6: Looking right (0, 8, 1, 3), the first element greater than 6 is 8. -> 8
  • Standing at 0: Looking right (8, 1, 3), the first element greater than 0 is 8. -> 8
  • Standing at 8: Looking right (1, 3), there are no elements greater than 8. -> -1
  • Standing at 1: Looking right (3), the first element greater than 1 is 3. -> 3
  • Standing at 3: Looking right (none), there are no elements. -> -1

• Expected Output Array: [8, 8, -1, 3, -1]

3. The Naive Approach and Its Limitations

The most intuitive brute-force approach involves checking every element's right-hand side using nested iteration.

Naive Implementation (Conceptual)

public int[] nextGreaterElementNaive(int[] arr) {
    int n = arr.length;
    int[] nge = new int[n];
    
    for (int i = 0; i < n; i++) {
        nge[i] = -1; // Default if no greater element is found
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
                nge[i] = arr[j];
                break; // Stop at the first greater element
            }
        }
    }
    return nge;
}

Complexity Analysis of Naive Approach

• Time Complexity: $\mathcal{O}(n^2)$ due to the nested loops checking elements to the right for every single index.
• Space Complexity: $\mathcal{O}(n)$ to store the output array (required for returning the answer). Note that modifying the input array in-place is discouraged in interviews.

4. Core Mental Model: The Light-Pole Analogy

Real-Life Analogy: Imagine you are standing on a street holding light poles of varying heights, looking toward the right. If you look ahead, you cannot see shorter light poles hidden behind a taller light pole. You will only see an increasing skyline of taller poles.

Why Forward Traversal Fails Efficiently

If you start traversing from the left, when you stand at index 3, you have no prior knowledge of what elements exist further to the right. Therefore, you cannot answer queries instantly.

Why Backward Traversal Works

If you traverse from the back (right to left), by the time you reach any index i, you have already processed, evaluated, and stored all elements to its right inside a stack.

5. Step-by-Step Evolution of the Optimized Solution

To maintain optimal efficiency, we combine a backward traversal with a monotonic decreasing stack.

The Decreasing Order Rule

1. As we traverse from right to left, we compare the current array element with the top of the stack.
2. Pop smaller or equal elements: Any element in the stack that is less than or equal to the current element can never serve as a next greater element for any preceding elements. Thus, we permanently pop them out.
3. Determine NGE:
   • If the stack is empty after popping, it means no greater element exists on the right $\rightarrow$ record -1.
   • If the stack is not empty, the top of the stack is our Next Greater Element $\rightarrow$ record stack.top().
4. Push current element: Push the current array element onto the stack to maintain our monotonic decreasing sequence.

6. Complete Flow Walkthrough

Let's trace the algorithm on a sample array: [3, 1, 2, 4, 6] traversing from right to left (indices 4 down to 0).

Array: [3, 1, 2, 4, 6]
Indices:  0  1  2  3  4

1. At Index 4 (value 6):

   • Stack is empty.
   • NGE for 6 = -1.
   • Push 6 to stack.
   • Stack: [6] | Output: [?, ?, ?, ?, -1]

2. At Index 3 (value 4):

   • Stack top is 6 (which is $> 4$). Do not pop.
   • NGE for 4 = 6.
   • Push 4 to stack.
   • Stack: [6, 4] | Output: [?, ?, ?, 6, -1]

3. At Index 2 (value 2):

   • Stack top is 4 (which is $> 2$). Do not pop.
   • NGE for 2 = 4.
   • Push 2 to stack.
   • Stack: [6, 4, 2] | Output: [?, ?, 4, 6, -1]

4. At Index 1 (value 1):

   • Stack top is 2 (which is $> 1$). Do not pop.
   • NGE for 1 = 2.
   • Push 1 to stack.
   • Stack: [6, 4, 2, 1] | Output: [?, 2, 4, 6, -1]

5. At Index 0 (value 3):

   • Stack top is 1 ($\le 3$) $\rightarrow$ Pop 1.
   • Next stack top is 2 ($\le 3$) $\rightarrow$ Pop 2.
   • Next stack top is 4 ($> 3$) $\rightarrow$ Stop popping.
   • NGE for 3 = 4.
   • Push 3 to stack.
   • Stack: [6, 4, 3] | Output: [4, 2, 4, 6, -1]

7. Pseudocode Implementation

Here is the clean, production-grade logic for solving the Next Greater Element problem:

import java.util.*;

public class NextGreaterElement {
    public static int[] findNextGreaterElement(int[] arr) {
        int n = arr.length;
        int[] nge = new int[n];
        Stack<Integer> stack = new Stack<>();

        // Traverse from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Pop all elements smaller than or equal to the current element
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }

            // If stack is empty, no greater element on the right
            if (stack.isEmpty()) {
                nge[i] = -1;
            } else {
                // The top of the stack is the next greater element
                nge[i] = stack.peek();
            }

            // Push the current element onto the stack
            stack.push(arr[i]);
        }

        return nge;
    }
}

8. Complexity Analysis: Why Is It $\mathcal{O}(n)$?

At first glance, seeing a while loop nested inside a for loop might lead one to assume an $\mathcal{O}(n^2)$ time complexity. However, amortized analysis proves otherwise.

Crucial Insight on Time Complexity: While the while loop can execute multiple times in a single iteration (e.g., popping several smaller elements at once), each element is pushed into the stack at most once and popped at most once throughout the entire traversal. Therefore, the total number of stack pop operations across all iterations combined can never exceed $n$.

Summary and Key Takeaways

• Monotonic Stack Definition: A stack engineered to maintain elements in a strict sorted order (increasing or decreasing) by popping violating elements during insertion.
• Problem Goal: The Next Greater Element problem requires identifying the first strictly greater element to the right for every index in an array.
• Naive vs. Optimal: Brute-force nested loops take $\mathcal{O}(n^2)$ time, whereas the monotonic stack approach optimizes this down to linear $\mathcal{O}(n)$ time.
• Traversal Strategy: Traversals for NGE problems must start from the back (right to left) to ensure elements on the right are already evaluated and ready in the stack.
• The Light-Pole Analogy: Taller elements block visibility of shorter elements behind them, justifying why smaller/equal elements are permanently popped from the stack.
• Amortized Analysis: Even with a while loop inside a for loop, the overall time complexity remains $\mathcal{O}(2n)$ because every element is pushed and popped at most once.
• Space Management: Auxiliary space uses $\mathcal{O}(n)$ for the stack and $\mathcal{O}(n)$ for the return array, avoiding bad practice in-place input mutation.