Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Next Greater Element I

EASYProblemSolveExternal Links

Description

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For every element in nums1, you need to find its next greater element in nums2. The next greater element of a value x in nums2 is the first element to the right of x in nums2 that is strictly larger than x. If no such element exists, the answer for that query is -1.

Return an array of the same length as nums1, where the i-th element is the next greater element of nums1[i] as found in nums2.

Since every element in nums1 also appears in nums2 (and all values are unique), you will always be able to locate each nums1 element within nums2.

Examples

Example 1

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

Output: [-1, 3, -1]

Explanation:

  • For nums1[0] = 4: Locate 4 in nums2 at index 2. Look right: nums2[3] = 2 is not greater than 4. No more elements. Answer: -1.
  • For nums1[1] = 1: Locate 1 in nums2 at index 0. Look right: nums2[1] = 3, and 3 > 1. Answer: 3.
  • For nums1[2] = 2: Locate 2 in nums2 at index 3. No elements to the right. Answer: -1.

Example 2

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

Output: [3, -1]

Explanation:

  • For nums1[0] = 2: Locate 2 in nums2 at index 1. Look right: nums2[2] = 3, and 3 > 2. Answer: 3.
  • For nums1[1] = 4: Locate 4 in nums2 at index 3. No elements to the right. Answer: -1.

Example 3

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

Output: [7, 7, 7, 7, 7]

Explanation: Every element in nums2 (except 7 itself) has 7 as its next greater element because 7 is at the far right and is larger than all other elements. Since all values in nums1 appear before 7 in nums2, each one maps to 7.

Constraints

  • 1 ≤ nums1.length ≤ nums2.length ≤ 1000
  • 0 ≤ nums1[i], nums2[i] ≤ 10^4
  • All integers in nums1 and nums2 are unique.
  • Every integer in nums1 also appears in nums2.

Editorial

Brute Force

Intuition

The most straightforward approach mirrors exactly what a human would do: for each number we need to look up, find where it sits in nums2, then scan to the right from that spot until we hit something bigger.

Imagine you have a row of buildings of different heights (nums2). Someone gives you a list of specific buildings (nums1) and asks: "For each of these buildings, what is the first taller building to its right?" You would walk to each building, face right, and look along the row until you spot a taller one — or reach the end.

This approach is simple to implement but does repeated work: for every query in nums1, we re-scan a portion of nums2. If many elements cluster near the start of nums2, we scan almost the entire array each time.

Step-by-Step Explanation

Let's trace through with nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]:

Step 1: Process nums1[0] = 4. Search for 4 in nums2 → found at index 2.

Step 2: Scan right from index 3: nums2[3] = 2. Is 2 > 4? No. 2 is smaller than 4.

Step 3: Reached end of nums2. No element to the right is greater than 4. Record ans[0] = -1.

  • Result so far: [-1]

Step 4: Process nums1[1] = 1. Search for 1 in nums2 → found at index 0.

Step 5: Scan right from index 1: nums2[1] = 3. Is 3 > 1? Yes! Found the first greater element immediately.

Step 6: Record ans[1] = 3. No need to scan further.

  • Result so far: [-1, 3]

Step 7: Process nums1[2] = 2. Search for 2 in nums2 → found at index 3.

Step 8: Index 3 is the last position in nums2. No elements to the right at all. Record ans[2] = -1.

  • Result so far: [-1, 3, -1]

Step 9: All queries processed. Final result: [-1, 3, -1].

Brute Force — Find and Scan for Each Query — For each element in nums1, we locate it in nums2 and then scan rightward to find the first larger value. The secondary row shows the growing result array.

Algorithm

  1. Create an empty result array.
  2. For each element num in nums1:
    a. Find the index pos of num in nums2 by linear search.
    b. Starting from pos + 1, scan rightward through nums2.
    c. If we find an element greater than num, record it and stop scanning.
    d. If we reach the end without finding one, record -1.
  3. Return the result array.

Code

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1,
                                   vector<int>& nums2) {
        vector<int> result;

        for (int num : nums1) {
            // Find num in nums2
            int pos = -1;
            for (int j = 0; j < nums2.size(); j++) {
                if (nums2[j] == num) {
                    pos = j;
                    break;
                }
            }

            // Scan right for next greater
            int nge = -1;
            for (int j = pos + 1; j < nums2.size(); j++) {
                if (nums2[j] > num) {
                    nge = nums2[j];
                    break;
                }
            }
            result.push_back(nge);
        }

        return result;
    }
};
class Solution:
    def nextGreaterElement(self, nums1: list[int],
                           nums2: list[int]) -> list[int]:
        result = []

        for num in nums1:
            # Find num in nums2
            pos = nums2.index(num)

            # Scan right for next greater
            nge = -1
            for j in range(pos + 1, len(nums2)):
                if nums2[j] > num:
                    nge = nums2[j]
                    break
            result.append(nge)

        return result
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
            // Find nums1[i] in nums2
            int pos = -1;
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) {
                    pos = j;
                    break;
                }
            }

            // Scan right for next greater
            result[i] = -1;
            for (int j = pos + 1; j < nums2.length; j++) {
                if (nums2[j] > nums1[i]) {
                    result[i] = nums2[j];
                    break;
                }
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(m × n)

Let m = nums1.length and n = nums2.length. For each of the m elements in nums1, we perform two scans of nums2: one to find the element (O(n)) and one to search for the next greater element (O(n) worst case). Total: m × (n + n) = O(m × n).

Space Complexity: O(1)

Excluding the output array, we use only a few integer variables (pos, nge, loop counters). No auxiliary data structures that scale with input size.

Why This Approach Is Not Efficient

The brute force approach performs redundant work. Consider: when we scan rightward from element 1 in nums2 = [1, 3, 4, 2], we pass through 3, 4, and 2 — learning the relative ordering of these elements. But this information is thrown away. When we later query for element 3 or element 2, we scan portions of the same array again, re-discovering facts we already encountered.

With m and n both up to 1,000, the worst case is roughly 1,000 × 1,000 = 1,000,000 operations. While this passes for the given constraints, it does not scale. If n were 10^5, the brute force would need 10^10 operations — far too slow.

The key insight is that we can compute the next greater element for every element in nums2 simultaneously in a single O(n) pass using a monotonic stack. Then answering each query from nums1 becomes a simple O(1) hash map lookup, bringing the total to O(m + n).

Optimal Approach - Monotonic Stack + Hash Map

Intuition

Imagine standing in a queue of people of different heights. You want to know, for each person, who is the first taller person standing behind them (to their right). Instead of checking each person one by one from scratch, a smarter strategy is to walk along the queue from left to right and keep a notepad of "unresolved" people — those who haven't found their taller neighbor yet.

As you encounter each new person:

  • Check your notepad (top of the stack). If the current person is taller than the person on top, that top person's question is answered — the current person IS their next taller neighbor. Pop them off the notepad and record the answer.
  • Keep popping as long as the current person is taller than the notepad's top. One tall person can resolve multiple shorter people at once.
  • Then add the current person to the notepad (they haven't found their taller neighbor yet).

This is the monotonic stack technique. The stack always holds elements in decreasing order from bottom to top. When a new element breaks this order (it is larger than the top), we know we have found the next greater element for those smaller stack entries.

After processing all of nums2, we store results in a hash map. For any element still on the stack (never popped), there is no next greater element — record -1. Finally, answering queries from nums1 is just a hash map lookup.

Step-by-Step Explanation

Let's trace with nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]:

Phase 1: Build the next-greater map using a monotonic stack on nums2

Step 1: Initialize an empty stack and an empty hash map.

  • Stack: [], Map: {}

Step 2: Process nums2[0] = 1. Stack is empty — nothing to compare. Push 1.

  • Stack: [1], Map: {}

Step 3: Process nums2[1] = 3. Stack top is 1. Is 3 > 1? Yes! Pop 1 and record map[1] = 3.

  • Stack: [], Map: {1: 3}

Step 4: Stack is now empty. Push 3.

  • Stack: [3], Map: {1: 3}

Step 5: Process nums2[2] = 4. Stack top is 3. Is 4 > 3? Yes! Pop 3 and record map[3] = 4.

  • Stack: [], Map: {1: 3, 3: 4}

Step 6: Stack is empty again. Push 4.

  • Stack: [4], Map: {1: 3, 3: 4}

Step 7: Process nums2[3] = 2. Stack top is 4. Is 2 > 4? No. Push 2 without popping.

  • Stack: [4, 2], Map: {1: 3, 3: 4}

Step 8: Array exhausted. Elements remaining in the stack (4 and 2) never found a greater element to their right. Record map[4] = -1, map[2] = -1.

  • Stack: [], Map: {1: 3, 3: 4, 4: -1, 2: -1}

Phase 2: Answer queries from nums1

Step 9: Look up each element: nums1[0]=4 → map[4]=-1, nums1[1]=1 → map[1]=3, nums1[2]=2 → map[2]=-1.

Result: [-1, 3, -1]

Monotonic Stack — Precomputing Next Greater Elements — Watch how the monotonic stack resolves next-greater-element queries as we traverse nums2 left to right. When a new element is larger than the stack top, we pop and record the mapping.

Algorithm

Phase 1: Build the next-greater-element map

  1. Initialize an empty stack and an empty hash map.
  2. For each element num in nums2 (left to right):
    a. While the stack is not empty AND num > stack top:
    • Pop the top element. Record map[popped] = num.
      b. Push num onto the stack.
  3. For each remaining element on the stack, record map[element] = -1.

Phase 2: Answer queries
4. For each element num in nums1:

  • Look up map[num] to get the answer.
  1. Return the result array.

Code

#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1,
                                   vector<int>& nums2) {
        unordered_map<int, int> ngeMap;
        stack<int> stk;

        // Phase 1: build map using monotonic stack
        for (int num : nums2) {
            while (!stk.empty() && num > stk.top()) {
                ngeMap[stk.top()] = num;
                stk.pop();
            }
            stk.push(num);
        }

        // Remaining elements have no next greater
        while (!stk.empty()) {
            ngeMap[stk.top()] = -1;
            stk.pop();
        }

        // Phase 2: answer queries
        vector<int> result;
        for (int num : nums1) {
            result.push_back(ngeMap[num]);
        }
        return result;
    }
};
class Solution:
    def nextGreaterElement(self, nums1: list[int],
                           nums2: list[int]) -> list[int]:
        nge_map = {}
        stack = []

        # Phase 1: build map using monotonic stack
        for num in nums2:
            while stack and num > stack[-1]:
                nge_map[stack.pop()] = num
            stack.append(num)

        # Remaining elements have no next greater
        while stack:
            nge_map[stack.pop()] = -1

        # Phase 2: answer queries
        return [nge_map[num] for num in nums1]
import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> ngeMap = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        // Phase 1: build map using monotonic stack
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                ngeMap.put(stack.pop(), num);
            }
            stack.push(num);
        }

        // Remaining elements have no next greater
        while (!stack.isEmpty()) {
            ngeMap.put(stack.pop(), -1);
        }

        // Phase 2: answer queries
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = ngeMap.get(nums1[i]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Let m = nums1.length and n = nums2.length. Phase 1 processes each element of nums2 exactly once. Although there is a while loop inside the for loop, each element is pushed onto the stack once and popped at most once, so the total number of push + pop operations is at most 2n. Phase 2 performs m hash map lookups, each O(1) on average. Total: O(n) + O(m) = O(m + n).

Space Complexity: O(n)

The stack can hold up to n elements in the worst case (when nums2 is sorted in decreasing order, no element is ever popped during the loop). The hash map stores one entry per element of nums2, which is O(n). Total auxiliary space: O(n).