Monotonic Stack for Next Greater Element

1. The "Next Greater Element" Problem

First, let's define the problem. Given an array of integers, your task is to find the next greater element (NGE) for each element. The NGE for an element x is the first element to its right that is larger than x. If no such element exists, the NGE is considered to be -1.

Example:
For the input array arr = [4, 5, 2, 10]:

• The next greater element for 4 is 5.
• The next greater element for 5 is 10.
• The next greater element for 2 is 10.
• For 10, there is no element to its right, so its NGE is -1.

The expected output would be [5, 10, 10, -1].

The Brute-Force Approach

The most straightforward way to solve this is with nested loops: for each element, you scan all the elements to its right to find the first one that is greater.

// Brute-force O(n^2) approach
for (int i = 0; i < n; i++) {
    int nge = -1;
    for (int j = i + 1; j < n; j++) {
        if (arr[j] > arr[i]) {
            nge = arr[j];
            break; // Found the first one, so we stop
        }
    }
    result[i] = nge;
}

This approach has a time complexity of O(n²), which is too slow for large arrays and would not be acceptable in an interview setting. This inefficiency motivates us to find a more optimal, linear-time solution.

To understand the problem and the shortcomings of the brute-force method in more detail, watch the first part of this video.

2. The Monotonic Stack: A More Efficient Tool

To achieve a linear time complexity of O(N), we need a smarter data structure. This is where the monotonic stack comes in.

A monotonic stack is a regular stack that maintains an additional property: its elements are always in a sorted order, either strictly increasing or strictly decreasing.

As the video explains, to find the Next Greater Element, we will use a monotonically decreasing stack. This seems counter-intuitive at first, but you'll soon see why it works perfectly.

3. The Algorithm: Right-to-Left Traversal

The key insight for an efficient solution is to process the array from right to left. Why? Because when you are at an element arr[i], you have already processed all the elements to its right. The stack can then be used to store potential candidates for the NGE.

Let's watch how this intuition is developed and applied.

Let's formalize the algorithm based on the video's explanation:

1. Initialize an empty stack (we'll use Deque<Integer> stack = new ArrayDeque<>(); in Java) and a result array res of the same size as the input.
2. Iterate through the input array from right to left (from index n-1 down to 0).
3. For each element currentElement = arr[i]:
   • While the stack is not empty AND the element at the top of the stack is less than or equal to currentElement:
     • Pop from the stack. These smaller elements can never be the NGE for currentElement or any other element to its left, because currentElement is closer and greater. So, they are no longer useful.
   • After the while loop:
     • If the stack is now empty, it means there is no greater element to the right of currentElement. Set res[i] = -1.
     • If the stack is not empty, the element at the top is the first greater element to the right. Set res[i] = stack.peek().
   • Finally, push currentElement onto the stack. It now becomes a potential NGE for the elements to its left.

By following this process, we ensure that the stack always contains elements in decreasing order from bottom to top.

4. Java Implementation and Complexity

Now, let's put this algorithm into Java code. The code is surprisingly concise and directly follows the logic we just outlined.

Here is a version of the code for your reference:

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Arrays;

class NextGreaterElement {
    public static int[] findNextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // Traverse the array from right to left
        for (int i = n - 1; i >= 0; i--) {
            int currentElement = nums[i];

            // 1. Pop elements from the stack that are smaller than or equal to the current element
            while (!stack.isEmpty() && stack.peek() <= currentElement) {
                stack.pop();
            }

            // 2. The top of the stack is the NGE, or -1 if the stack is empty
            if (stack.isEmpty()) {
                result[i] = -1;
            } else {
                result[i] = stack.peek();
            }

            // 3. Push the current element onto the stack for future comparisons
            stack.push(currentElement);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10};
        int[] nge = findNextGreaterElements(arr);
        // Expected output: [5, 10, 10, -1]
        System.out.println("Input array: " + Arrays.toString(arr));
        System.out.println("Next Greater Elements: " + Arrays.toString(nge));
    }
}

Complexity Analysis

At first glance, the nested while loop inside the for loop might make you think the complexity is O(n²). However, it is not.

• Time Complexity: O(N)
  Each element of the array is pushed onto the stack exactly once. Each element is also popped from the stack at most once. Since each element experiences a constant number of stack operations (one push and at most one pop) over the entire execution, the total time complexity is linear, or O(N). This is a concept known as amortized analysis.

• Space Complexity: O(N)
  In the worst-case scenario (e.g., an array sorted in decreasing order like [10, 8, 5, 2]), the stack will hold all N elements at once. Therefore, the space required is proportional to the size of the input array.

Conclusion

Congratulations! You've just learned one of the most elegant and efficient stack patterns. The monotonic stack is a powerful tool for your interview and competitive programming arsenal. It's a great example of how augmenting a basic data structure with a simple rule can lead to significant performance gains.

Key Takeaways:

• The monotonic stack is a stack that maintains its elements in a sorted (increasing or decreasing) order.
• The Next Greater Element problem can be solved in O(N) time using a monotonic stack with a right-to-left traversal.
• The core logic involves popping elements from the stack that violate the monotonic property relative to the current element being processed.
• This pattern can be adapted to solve similar problems like "Next Smaller Element," "Previous Greater Element," and "Previous Smaller Element."

Preview of the next lesson:
We have now covered two important applications of stacks. In the next lesson, we will shift our focus to another fundamental linear data structure: the queue. You will learn how to implement a queue using both a circular array and a linked list, understanding its FIFO (First-In, First-Out) behavior and its own set of unique applications.