#496

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Next Greater Element I

Find the next greater element for each number in nums1 from the nums2 array using an optimized approach.

Problem Statement

You are given two integer arrays, nums1 and nums2, where nums1 is a subset of nums2. The task is to find the next greater element for each element in nums1, which refers to the first element that is greater and appears to the right of that element in nums2. If no greater element exists, the result should be -1.

For each element in nums1, you must identify its position in nums2 and find the next greater element to the right. If no such element exists, return -1. An efficient solution involves array scanning and hash lookups, avoiding a brute force method that would be too slow.

Examples

Example 1

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

Output: [-1,3,-1]

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

4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2

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

Output: [3,-1]

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

2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Constraints

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

Solution Approach

Stack-based Monotonic Approach

A monotonic stack approach can be used to find the next greater elements efficiently. Traverse nums2 from right to left, using the stack to keep track of the next greater elements for the current element. Each element is processed once, allowing for a time complexity of O(n), where n is the length of nums2.

Hash Table Lookup

After processing nums2 with the stack, use a hash table to map each element in nums2 to its next greater element. This allows you to efficiently look up the next greater element for each number in nums1 in constant time, reducing the overall time complexity of the solution.

Final Result Construction

With the hash table ready, iterate through nums1 and for each element, retrieve its next greater element from the table. If no greater element exists, append -1. This step ensures that the solution works in O(m) time, where m is the length of nums1.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The overall time complexity is O(n + m), where n is the length of nums2 and m is the length of nums1. The space complexity is O(n) due to the hash table and stack.

What Interviewers Usually Probe

Candidates should be able to explain how the stack is used to maintain the next greater elements in a monotonic manner.
Look for a clear understanding of how hash tables optimize the lookup process after processing nums2.
Candidates should discuss the time and space complexities and how they are optimized compared to a brute-force solution.

Common Pitfalls or Variants

Common pitfalls

Not using the stack to maintain the next greater elements in a monotonic order, which leads to a less efficient solution.
Overlooking the need to map elements of nums2 to their next greater element using a hash table, leading to slower lookups.
Misunderstanding the problem constraints, leading to inefficient or incorrect handling of array indices.

Follow-up variants

Handling multiple queries for different nums1 arrays with the same nums2 array.
Optimizing further using additional data structures, like trees or heaps, to support different types of range queries.
Adapting the approach for finding the previous greater element instead of the next greater element.

FAQ

What is the time complexity of the Next Greater Element I problem?

The time complexity is O(n + m), where n is the length of nums2 and m is the length of nums1, due to the stack processing and hash table lookups.

How can the stack be used in the Next Greater Element I problem?

The stack is used to store elements of nums2 while traversing it from right to left, ensuring that we can find the next greater element for each item in constant time.

What is the role of the hash table in solving Next Greater Element I?

The hash table stores the next greater element for each element in nums2, allowing for constant time lookup when processing nums1.

How does the space complexity of this solution compare to other approaches?

The space complexity is O(n), where n is the length of nums2, due to the stack and hash table. This is efficient compared to a brute-force approach, which would require O(m * n) space.

Can this solution be adapted for similar problems?

Yes, this approach can be adapted to solve similar problems, such as finding the previous greater element or handling different types of range queries.

terminal

Solution

Solution 1: Monotonic Stack

We can traverse the array $\textit{nums2}$ from right to left, maintaining a stack $\textit{stk}$ that is monotonically increasing from top to bottom. We use a hash table $\textit{d}$ to record the next greater element for each element.

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#1124 longest well performing interval #456 132 pattern #581 shortest unsorted continuous subarray