Course4all
Join us on telegram
Home/dsa/Stack/Next Greater Element I

Next Greater Element I

Master this topic with zero to advance depth.

Next Greater Element I

Find the next greater element for each element in nums1 within nums2. The next greater element of x in nums2 is the first element to its right that is larger than x.

Visual Representation

nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2] Processing nums2 to find next greater: 1. 1: Stack [1] 2. 3: 3 > 1. Map[1]=3. Pop, Push 3. Stack [3] 3. 4: 4 > 3. Map[3]=4. Pop, Push 4. Stack [4] 4. 2: 2 < 4. Push 2. Stack [4, 2] Result Map: {1:3, 3:4} For nums1: 4 -> -1, 1 -> 3, 2 -> -1 Output: [-1, 3, -1]
Easy

Examples

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

Level I: Brute Force (Nested Loops)

Intuition

For each element in nums1, find its position in nums2, then linearly scan rightward to find the first element greater than it. Simple, but performs redundant scans.

⏱ O(M * N) where M is nums1.length and N is nums2.length.💾 O(1) excluding the output array.
java
import java.util.Arrays;

public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = -1;
            boolean found = false;
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) found = true;
                else if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2})));
    }
}
Approach 2

Level II: Pre-located Search (Map + Scan)

Intuition

Instead of linearly searching for each element of nums1 in nums2 every time, we can pre-store the indices of all elements in nums2 in a hash map. This allows us to jump directly to the correct starting point in nums2 for the scan, eliminating the 'find index' part of the brute force.

⏱ O(N + M*N) worst case, but faster in practice.💾 O(N) to store indices of nums2.
java
import java.util.*;
public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) map.put(nums2[i], i);
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = -1;
            int start = map.get(nums1[i]);
            for (int j = start + 1; j < nums2.length; j++) {
                if (nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Monotonic Stack + HashMap)

Intuition

Use a monotonic decreasing stack to find the next greater element for all elements in nums2 in a single pass. Store the results in a hash map for O(1) lookups when processing nums1.

⏱ O(N + M) where N is nums2.length, M is nums1.length💾 O(N)

Detailed Dry Run

Num (nums2)StackMap UpdateAction
1[1]-Push
3[3]1 -> 3Pop 1, Push 3
4[4]3 -> 4Pop 3, Push 4
2[4, 2]-Push
java
import java.util.*;

public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) map.put(stack.pop(), num);
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) res[i] = map.getOrDefault(nums1[i], -1);
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] res = sol.nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
        System.out.println(Arrays.toString(res)); // [-1, 3, -1]
    }
}

⚠️ Common Pitfalls & Tips

Ensure nums1 is actually a subset of nums2 as per problem constraints. The stack approach only works for finding the next greater element.

← Previous QuestionDaily Temperatures
Next Question →Next Greater Element II