Next Greater Element I — Practice

Problem

The next greater element of some element x in an array is the first greater element to its right. Given two arrays nums1 and nums2 (nums1 is a subset of nums2), for each element in nums1, find its next greater element in nums2. If none exists, use -1.

Examples

Example 1

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

Explanation: 4 has no greater element to its right in nums2; 1's next greater is 3; 2 has none.

Constraints

•1 <= nums1.length <= nums2.length <= 1000
•All integers are unique

Hints

Hint 1

Precompute the next-greater-element answer for every number in nums2 once, using a monotonic stack — then look up nums1's answers from that precomputed map.

Hint 2

Don't recompute per-query — that turns an O(n) precomputation into an O(n*m) brute force.

Solutions

public int[] nextGreaterElementBruteForce(int[] nums1, int[] nums2) {
    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        int target = nums1[i];
        int j = 0;
        while (nums2[j] != target) j++; // find target's position in nums2
        int nextGreater = -1;
        for (int k = j + 1; k < nums2.length; k++) {
            if (nums2[k] > target) { nextGreater = nums2[k]; break; }
        }
        result[i] = nextGreater;
    }
    return result;
}

Time: O(n*m) · Space: O(1) extra beyond the output