Next Greater Element I

Difficulty: Easy | Acceptance: 76.10% | Paid: No Topics: Array, Hash Table, Stack, Monotonic Stack

The next greater element of some element x in an array is the first element to the right of x that has a value strictly greater than x.

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

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

• Examples
• Constraints
• Brute Force
• Monotonic Stack

Examples

Example 1

Input:

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

Output:

[-1,3,-1]

Explanation: The next greater element for each value in nums1 is as follows:

• 4 is underlined in nums2 = [1,3,4,2]. There is no element to the right of 4 that is greater than 4, so the answer is -1.
• 1 is underlined in nums2 = [1,3,4,2]. The next greater element of 1 is 3.
• 2 is underlined in nums2 = [1,3,4,2]. There is no element to the right of 2 that is greater than 2, so the answer is -1.

Example 2

Input:

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

Output:

[3,-1]

Explanation: The next greater element for each value in nums1 is as follows:

• 2 is underlined in nums2 = [1,2,3,4]. The next greater element of 2 is 3.
• 4 is underlined in nums2 = [1,2,3,4]. There is no element to the right of 4 that is greater than 4, so the answer is -1.

Constraints

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10⁴
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.

Brute Force

Intuition For each element in nums1, find its position in nums2 and scan right to find the first greater element.

Steps

• For each element in nums1, find its index in nums2
• Starting from that index, scan right to find the first element greater than it
• If found, add to result; otherwise add -1

from typing import List

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        for num in nums1:
            index = nums2.index(num)
            next_greater = -1
            for i in range(index + 1, len(nums2)):
                if nums2[i] > num:
                    next_greater = nums2[i]
                    break
            result.append(next_greater)
        return result

Complexity

• Time: O(n × m) where n = nums1.length, m = nums2.length
• Space: O(n) for the result array
• Notes: Simple but inefficient for large inputs

Monotonic Stack

Intuition Use a monotonic decreasing stack to efficiently find next greater elements for all values in nums2, then look up results for nums1 using a hash map.

Steps

• Iterate through nums2 using a stack
• Maintain a decreasing stack (elements are in decreasing order from bottom to top)
• When we find an element greater than stack top, it’s the next greater element for stack top
• Store these mappings in a hash map
• Look up results for each element in nums1

from typing import List

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        next_greater = {}
        stack = []
        
        for num in nums2:
            while stack and stack[-1] < num:
                next_greater[stack.pop()] = num
            stack.append(num)
        
        return [next_greater.get(num, -1) for num in nums1]

Complexity

• Time: O(n + m) where n = nums1.length, m = nums2.length
• Space: O(m) for the hash map and stack
• Notes: Optimal solution with linear time complexity