L6. Next Greater Element - II | Stack and Queue Playlist

Welcome back to the PlayBook Library technical notes for Data Structures and Algorithms. In this chapter, we explore Next Greater Element II, expanding on the foundational monotonic stack principles established in the first part. Here, we tackle the added complexity of treating the input array as a circular array, ensuring that elements near the end can wrap around to find their next greater element.

1. Problem Statement & The Circular Array Twist

In standard Next Greater Element I, given an array of integers, you look strictly to the right of each element to find the first element strictly greater than it. If none exists, the answer is -1.

In Next Greater Element II, the array is treated as circular. This means if you reach the end of the array without finding a greater element, you must continue your search by wrapping around to the beginning of the array.

Real-Life Analogy: The Round Table Seating

Imagine a group of people sitting around a circular conference table, each holding a numbered card representing their height. When someone stands up and looks around the table clockwise to find the first person taller than them, they do not stop when they reach the last seat at the end of the row. Instead, their gaze continues past the end of the line, wrapping around to the very first seat at the front of the room until they find a taller person or complete a full circle.

Walkthrough Example

Consider the following input array:

Array: [2, 10, 12, 1, 11]
Indices: 0,  1,   2, 3,  4

Let's find the Next Greater Element (NGE) for each position:

• For 2 (Index 0): Looking right, 10 is greater. -> NGE = 10
• For 10 (Index 1): Looking right, 12 is greater. -> NGE = 12
• For 12 (Index 2): Looking right yields no greater element. Wrapping around: 1, then 10. None are greater than 12. -> NGE = -1
• For 1 (Index 3): Looking right, 11 is greater. -> NGE = 11
• For 11 (Index 4): Looking right yields nothing. Wrapping around: 2 (no), 10 (no), 12 (yes, 12 > 11). -> NGE = 12

2. Naive Brute Force Approach ($O(N^2)$)

The most intuitive brute force solution is to visit every element and search for its next greater element using nested loops that account for the circular wrap-around.

Algorithm Design

1. Initialize an answer array NG of size n with default values.
2. Outer loop i from 0 to n - 1 to target each element.
3. Inner loop j runs from i + 1 to i + n - 1 (representing a span of $N-1$ elements to the right).
4. Access elements using modulo arithmetic: index = j % n.
5. If arr[index] > arr[i], record arr[index] as the NGE and break.

Naive Code Structure (Conceptual)

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] ng = new int[n];
    Arrays.fill(ng, -1);

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= i + n - 1; j++) {
            int index = j % n;
            if (nums[index] > nums[i]) {
                ng[i] = nums[index];
                break;
            }
        }
    }
    return ng;
}

Complexity Analysis

• Time Complexity: $O(N^2)$ due to the nested traversal for each of the $N$ elements.
• Space Complexity: $O(N)$ to store the output array ng.

Interviewer Critique: An $O(N^2)$ solution is inefficient for large datasets. We must optimize this using a Monotonic Stack.

3. The Mental Model: Virtual Array Doubling

To leverage our monotonic stack approach from NGE-I without physically duplicating the array in memory (which wastes space and allocation time), we use a virtual doubling technique.

How Virtual Doubling Works

Imagine the array is concatenated with a clone of itself in your mind:

Original:    [2, 10, 12, 1, 11]  (Indices 0 to 4)
Virtual Extension: [2, 10, 12, 1, 11]  (Indices 5 to 9)

• Total virtual length = $2N$
• Indices range from 0 to 2N - 1.
• Any virtual index j maps back to the real array via modulo arithmetic: j % n.

4. Optimized Solution Using Monotonic Stack ($O(N)$)

By traversing backward from the last hypothetical index ($2N - 1$) down to 0, we can maintain elements in a decreasing monotonic stack. This ensures that every element gets compared against potential greater elements in its circular future.

Step-by-Step Execution Trace

Let's trace nums = [2, 10, 12, 1, 11] ($N = 5$, Virtual indices: $0$ to $9$).

1. Start at $i = 9$ (Virtual index for last element 11):
   • Stack is empty. Push 11.
2. $i = 8$ (1):
   • Stack top (11) is greater than 1. Push 1. Stack: [11, 1].
3. $i = 7$ (12):
   • Stack top (1) is smaller than 12 $\rightarrow$ pop 1.
   • Next stack top (11) is smaller than 12 $\rightarrow$ pop 11.
   • Stack is empty. Push 12. Stack: [12].
4. $i = 6$ (10):
   • Stack top (12) is greater than 10. Push 10. Stack: [12, 10].
5. $i = 5$ (2):
   • Stack top (10) is greater than 2. Push 2. Stack: [12, 10, 2].
6. $i = 4$ (11 - First real pass traversal starts here):
   • We are now in the real array region ($i < N$), so we record answers.
   • Stack top (2) < 11 $\rightarrow$ pop 2.
   • Stack top (10) < 11 $\rightarrow$ pop 10.
   • Next stack top (12) > 11 $\rightarrow$ NGE for index 4 is 12.
   • Push 11. Stack: [12, 11].
7. $i = 3$ (1):
   • Stack top (11) > 1 $\rightarrow$ NGE for index 3 is 11.
   • Push 1. Stack: [12, 11, 1].
8. $i = 2$ (12):
   • Pop 1, pop 11, pop 12 (all $\le 12$). Stack is empty $\rightarrow$ NGE = -1.
   • Push 12. Stack: [12].
9. $i = 1$ (10):
   • Stack top (12) > 10 $\rightarrow$ NGE for index 1 is 12.
   • Push 10. Stack: [12, 10].
10. $i = 0$ (2):
    • Stack top (10) > 2 $\rightarrow$ NGE for index 0 is 10.
    • Push 2. Stack: [12, 10, 2].

5. Complete Java Implementation

Here is the clean, production-ready Java code implementing the virtual circular monotonic stack approach.

import java.util.Stack;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ng = new int[n];
        Stack<Integer> stack = new Stack<>();

        // Traverse hypothetically from 2N - 1 down to 0
        for (int i = 2 * n - 1; i >= 0; i--) {
            int currentIndex = i % n;

            // Maintain monotonic decreasing stack
            while (!stack.isEmpty() && stack.peek() <= nums[currentIndex]) {
                stack.pop();
            }

            // Record answer only for the real array elements (i < n)
            if (i < n) {
                if (stack.isEmpty()) {
                    ng[i] = -1;
                } else {
                    ng[i] = stack.peek();
                }
            }

            // Push current element onto the stack
            stack.push(nums[currentIndex]);
        }

        return ng;
    }
}

6. Complexity Analysis Summary

7. Summary and Key Takeaways

• Circular Array Handling Without Duplication: Avoid physically doubling arrays in memory; instead, use virtual indexing via modulo arithmetic (i % n) across a $2N-1$ loop range.
• Monotonic Stack Pattern: Maintain elements in a decreasing order in the stack by popping smaller or equal elements before processing the current element.
• Two-Pass Simulation: The first pass (from $2N-1$ down to $N$) populates the stack with future circular candidates, and the second pass (from $N-1$ down to $0$) records the actual answers.
• Strict Conditional Recording: Only record answers into the result array when the hypothetical index falls within the real array bounds ($i < n$).
• Optimal Efficiency: Achieves an optimal $O(N)$ time complexity, reducing the naive $O(N^2)$ solution down to linear performance.