496. Next Greater Element I - Explanation

Problem Link

Description

The next greater element of some element x in an array is the first greater element that is to the right of x in the array.

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

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.

Example 1:

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

Output: [-1,3,-1]

Explanation:

• There is no next greater element for 4.
• 3 is the next greater element for 1.
• There is no next greater element for 2.

Example 2:

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

Output: [3,-1]

Explanation:

• 3 is the next greater element for 2.
• There is no next greater element for 4.

Constraints:

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

Follow up: Could you find an O(nums1.length + nums2.length) solution?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums2)
        res = []
        for num in nums1:
            nextGreater = -1
            for i in range(n - 1, -1, -1):
                if nums2[i] > num:
                    nextGreater = nums2[i]
                elif nums2[i] == num:
                    break
            res.append(nextGreater)
        return res

Time & Space Complexity

• Time complexity: $O(m * n)$
• Space complexity: $O(1)$

Where $m$ is the size of the array $nums1$ and $n$ is the size of the array $nums2$.

---

2. Hash Map

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1Idx = {num : i for i, num in enumerate(nums1)}
        res = [-1] * len(nums1)

        for i in range(len(nums2)):
            if nums2[i] not in nums1Idx:
                continue
            for j in range(i + 1, len(nums2)):
                if nums2[j] > nums2[i]:
                    idx = nums1Idx[nums2[i]]
                    res[idx] = nums2[j]
                    break
        return res

Time & Space Complexity

• Time complexity: $O(m * n)$
• Space complexity: $O(m)$

Where $m$ is the size of the array $nums1$ and $n$ is the size of the array $nums2$.

---

3. Stack

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1Idx = {num : i for i, num in enumerate(nums1)}
        res = [-1] * len(nums1)

        stack = []
        for i in range(len(nums2)):
            cur = nums2[i]
            while stack and cur > stack[-1]:
                val = stack.pop()
                idx = nums1Idx[val]
                res[idx] = cur
            if cur in nums1Idx:
                stack.append(cur)
        return res

Time & Space Complexity

• Time complexity: $O(m + n)$
• Space complexity: $O(m)$

Where $m$ is the size of the array $nums1$ and $n$ is the size of the array $nums2$.