LeetCode 496 Next Greater Element I - From Brute Force to Optimized - Solution Explanation (Easy, Java, O(n))

• LeetCode 496. Next Greater Element I

The LeetCode problem "496. Next Greater Element I" asks us to find the first greater element to the right of each element in nums1 within nums2, where nums1 is a subset of nums2. If no such element exists, return -1. Below, we discuss two solutions: a brute force approach and an optimized solution using a monotonic stack, both implemented in Java.

Brute Force Solution

Approach

The brute force solution iterates through each element in nums1. For each element, it:

1. Searches for that element in nums2.
2. Once found, scans the elements to the right in nums2 to find the first element greater than the current element.
3. If a greater element is found, stores it in the result array; otherwise, stores -1.

Complexity Analysis

• Time Complexity: O(n1 * n2), where n1 is the length of nums1 and n2 is the length of nums2. For each element in nums1, we potentially scan most of nums2 to find the element and then scan the remaining elements to find the next greater one.
• Space Complexity: O(1), excluding the output array, as we only use a few variables.

Code

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] ans = new int[len1];

        for (int i = 0; i < len1; i++) {
            // Initialize ans[i] to -1
            ans[i] = -1;
            // Find nums1[i] in nums2
            for (int j = 0; j < len2; j++) {
                if (nums2[j] == nums1[i]) {
                    // Look for the first next greater element
                    for (int k = j + 1; k < len2; k++) {
                        if (nums2[k] > nums1[i]) {
                            ans[i] = nums2[k];
                            break; // Stop after finding the first greater element
                        }
                    }
                    break; // No need to continue searching nums2 after finding nums1[i]
                }
            }
        }
        return ans;
    }
}

Optimized Solution (Monotonic Stack)

Approach

The optimized solution uses a monotonic stack to efficiently find the next greater element for each element in nums2, then maps these results to nums1. The steps are:

1. Initialize an empty stack and a hash map to store the next greater element for each number in nums2.
2. Iterate through nums2. For each element:
   • While the stack is not empty and the current element is greater than the stack's top element, pop the stack and map the popped element to the current element (as it is the next greater).
   • Push the current element onto the stack.
3. After processing nums2, any elements remaining in the stack have no next greater element, so map them to -1.
4. Create the result array by looking up each nums1 element in the hash map.

This approach ensures we process each element in nums2 once and use the stack to maintain a decreasing order of elements, making it efficient.

Complexity Analysis

• Time Complexity: O(n1 + n2), where n1 is the length of nums1 and n2 is the length of nums2. Each element in nums2 is pushed and popped at most once (O(n2)), and each element in nums1 is looked up in the hash map (O(n1)).
• Space Complexity: O(n2) for the stack and hash map, as they store up to n2 elements.

Code

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

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // Hash map to store next greater element for each number in nums2
        Map<Integer, Integer> nextGreater = new HashMap<>();
        // Stack to keep track of elements waiting for their next greater
        Stack<Integer> stack = new Stack<>();

        // Process nums2 to find next greater elements
        for (int num : nums2) {
            // While stack is not empty and current number is greater than stack top
            while (!stack.isEmpty() && stack.peek() < num) {
                // Pop element and map it to current number (next greater)
                nextGreater.put(stack.pop(), num);
            }
            stack.push(num);
        }

        // Elements remaining in stack have no next greater element
        while (!stack.isEmpty()) {
            nextGreater.put(stack.pop(), -1);
        }

        // Create result array by mapping nums1 elements to their next greater
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = nextGreater.get(nums1[i]);
        }

        return ans;
    }
}

Summary

• The brute force solution is straightforward but inefficient for large inputs due to its O(n1 n2) time complexity. It has been corrected to ensure it captures the first* greater element by adding a break statement.
• The optimized solution uses a monotonic stack to achieve O(n1 + n2) time complexity, making it suitable for larger inputs. It leverages a stack to track elements waiting for their next greater element and a hash map for quick lookups, meeting the follow-up challenge's requirement.