{x}
blog image

Next Greater Element I

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 same array.

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.

 

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: 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]
Explanation: 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.

 

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

Solution Explanation: Next Greater Element I

This problem asks us to find the next greater element for each element in nums1 from the array nums2. The "next greater element" is defined as the first element to the right that is strictly larger. If no such element exists, we return -1.

The optimal solution uses a monotonic stack and a hash map (or dictionary) for efficient lookup. Let's break down the approach:

1. Monotonic Stack:

A monotonic stack is a stack that maintains a specific order (either strictly increasing or strictly decreasing). In this case, we use a decreasing monotonic stack. The stack stores elements from nums2.

2. Hash Map (or Dictionary):

We use a hash map (d in the code examples) to store the results efficiently. The keys are the elements from nums2, and the values are their corresponding next greater elements.

3. Algorithm:

  • Initialization: Create an empty monotonic stack stk and an empty hash map d.
  • Iteration: Iterate through nums2 from right to left (this is crucial for finding the next greater element to the right).
  • Stack Manipulation: For each element x in nums2:
    • While the stack is not empty and the top element of the stack is smaller than x, pop elements from the stack. This ensures that the stack always maintains a decreasing order. The popped elements have x as their next greater element.
    • If the stack is not empty after popping, the top element of the stack is the next greater element for x. Store this in the hash map: d[x] = stk[-1] (Python), d.put(x, stk.peek()) (Java), etc.
    • Push x onto the stack.
  • Result Retrieval: Iterate through nums1. For each element x in nums1, look up its next greater element in the hash map d. If it's not found (meaning no next greater element exists), return -1.

Time Complexity: O(m + n), where m is the length of nums1 and n is the length of nums2. We iterate through nums2 once and nums1 once. The stack operations (push and pop) take constant time on average.

Space Complexity: O(n), primarily due to the hash map d which stores at most n entries (one for each element in nums2). The stack stk can also use at most n space in the worst-case scenario.

Code Examples (with detailed comments):

The code examples in Python, Java, C++, Go, TypeScript, Rust and Javascript provided in the original response demonstrate the algorithm effectively. Each example follows the same basic steps outlined above, adapted to the syntax of each language. The comments within the code provide further clarity on the individual steps. Refer to those examples for a practical implementation of this solution.