Next Greater Element I – 496. LeetCode

Imagine you have two lists of numbers. For each number in the first list, you want to find the next larger number in the second list that comes after it. If no such number exists, you return -1. This problem is about efficiently finding these “next greater elements”.

Brute Force Approach

public class NextGreaterElementI {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int current = nums1[i];
            int nextGreater = -1;
            boolean found = false;
            for (int num : nums2) {
                if (num == current) {
                    found = true; // Start looking for next greater
                } else if (found && num > current) {
                    nextGreater = num;
                    break;
                }
            }
            result[i] = nextGreater;
        }
        return result;
    }
}

• Iterate though each number in nums 1.
• For each number, scan nums2 to find its first occurrence, then look for the next greater number.
• If a greater number is found, update the result; otherwise, set it to -1.

Optimal Approach

Algorithm & Data Structure

• Algorithm: Monotonic Decreasing Stack

• Data Structure: Stack and HashMap

Instead of scanning nums2 repeatedly for each element in nums1, preprocess nums2 to find the “next greater element” for all its numbers in a single pass. Use a stack to keep track of numbers for which the next greater number has not yet been found. Use a map to store the results for quick lookup when processing nums1.

• We only need the “next” greater number, making the stack ideal for maintaining potential candidates.

• The order matters, so a linear scan with a stack ensures efficient processing.

Steps:

1. Traverse nums2 from left to right.

2. Use a stack to keep track of numbers for which the “next greater element” is not yet found.

3. For each number, pop the stack while the current number is greater, and map the popped number to the current number.

4. After processing nums2, use the map to populate the results for nums1.

import java.util.HashMap;
import java.util.Stack;

public class NextGreaterElementI {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>(); // To store next greater element
        Stack<Integer> stack = new Stack<>(); // Monotonic decreasing stack

        // Process nums2 to find next greater elements
        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                map.put(stack.pop(), num); // Next greater for stack.peek() is num
            }
            stack.push(num); // Push current number onto stack
        }

        // Populate results for nums1
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.getOrDefault(nums1[i], -1); // Get next greater or -1
        }

        return result;
    }
}

Line By Line Explanation

Step 1: Prepare Data Structures

HashMap<Integer, Integer> map = new HashMap<>(); 
Stack<Integer> stack = new Stack<>();

• A HashMap is prepared to store pairs of number, it records which element is the next greater number.
• A Stack is initialized to temporarily hold numbers while we’re scanning the array.
• The map ensures quick lookups for the next greater number for any given element.
• The stack helps efficiently track numbers who greater match has not been found yet. it ensures we process the line in an organized way.

Step 2: Iterate through nums2

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

• Start iterating through num2, one num at a time.
• If there’s an element on the stack (stack.peek()) that is smaller than the current num, you record the current element as the next greater in the stack.
  • stack.pop(): Removes the smaller number from the stack since we’ve found the greater match.
  • map.put(): Maps the smaller number to the current larger number.
• If no element in the stack is smaller, you simply add the current element to the stack.
• The stack maintains a “monotonic decreasing order”, meaning it only hold numbers that haven’t been matched to larger numbers.

Step 3: Process Map

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

• For each element in nums1, you perform lookup in map to find the next greater number.
• If they aren’t in map, it means no number was found, so assign -1.
• This loop ensures that the results are in the same order as nums1.

Step 4: Return the Results

return result;

• This is the final output you’re interested in: who’s the next taller person for each friend.

Why this code was designed this way:

• Efficiency: The stack ensures we process each element in nums2 only once, and the map avoids redundant computations for nums1.

• Clarity: Separating the processing of nums2 and result population for nums1 keeps the logic modular.

• Scalability: The O(n + m) complexity makes this approach suitable for large input sizes.