Python 0496.py
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
result = []
pos = {}
for i in range(len(nums2)):
pos[nums2[i]] = i
for i in nums1:
j = pos[i] + 1
while j < len(nums2) and nums2[j] < i:
j += 1
if j == len(nums2):
result.append(-1)
else:
result.append(nums2[j])
return result
Difficulty
and has an acceptance rate of about 77% (2+ million submissions).
Typical patterns to solve this problem:
- Array
- Hash Table
- Monotonic Stack
- Stack
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a class Solution with a method nextGreaterElement. The method receives two integer lists, nums1 and nums2, and returns a list containing, for each element of nums1, the first greater element that appears to its right in nums2. If no such element exists, -1 is placed in the result. The algorithm proceeds by first building a positional map for quick index lookup in nums2, then iterating over each element of nums1 to locate its next greater element using a linear scan that stops as soon as a larger value is found or the end of nums2 is reached.
Key Steps
The first step creates an empty list that will hold the final answers.
result = []
Next, a dictionary named pos is populated with the index of every value in nums2. This enables constant-time retrieval of the starting position for each search.
pos = {}
for i in range(len(nums2)):
pos[nums2[i]] = i
The core loop processes each element i from nums1. For each element, the algorithm retrieves its index in nums2 from the pos map and begins the search one position to the right.
for i in nums1:
j = pos[i] + 1
A while loop advances j while it remains within the bounds of nums2 and the current candidate nums2[j] is not greater than the target value i. The loop stops either when a greater element is found or when the end of nums2 is reached.
while j < len(nums2) and nums2[j] < i:
j += 1
After the scan, a conditional determines whether a valid greater element was located. If j has reached the length of nums2, the algorithm appends -1 to indicate the absence of a greater element. Otherwise, it appends the found greater value.
if j == len(nums2):
result.append(-1)
else:
result.append(nums2[j])
Finally, the method returns the populated result list.
return result
Edge Cases Handled
When an element from nums1 appears at the last position of nums2, the initial j value becomes equal to the length of nums2. The subsequent while loop is bypassed, and the conditional correctly records -1 because there are no elements to the right. This also covers the scenario where nums1 contains a value that has no greater element anywhere to its right in nums2.
If nums2 contains duplicate values, the dictionary pos will store the index of the last occurrence of each value because later assignments overwrite earlier ones. Consequently, the search for the next greater element begins after the final occurrence, which aligns with the requirement to consider only elements that appear after the target in nums2.
When nums1 is empty, the outer loop does not execute, and the method returns an empty result list, reflecting the expected behavior for an empty input set.
Performance Optimizations
The construction of the pos dictionary provides a direct mapping from each value in nums2 to its index, eliminating the need for repeated linear scans to locate the starting point for each query. This reduces the overhead of locating the initial position for each element of nums1 to constant time.
The inner while loop advances the index j only until a greater element is found, avoiding unnecessary traversal of the entire remainder of nums2 when a suitable candidate appears early. By breaking out of the loop as soon as the condition nums2[j] >= i is satisfied, the algorithm minimizes the number of comparisons performed for each element of nums1.
The use of a single list result that is appended to incrementally avoids the creation of intermediate collections, thereby keeping memory usage focused on the essential output structure.
ELI5 - Simplified Explanation
Imagine two long trains of numbered blocks. The first train is short, and the second train is much longer. The goal is to look at each block in the short train and find the very next block in the long train that is taller than the one in your hand.
First, a special map is created to remember exactly which spot every number occupies in the long train. This acts like a treasure map so you never have to search through the whole train from the start.
After checking where the number is, you step forward in the long train one spot at a time. If the next block is still shorter than the one you are holding, you keep walking forward to the next one. You keep moving until you finally see a block that is taller, or until you run out of blocks entirely.
If you find a taller block, you write that number down on a new list. If you reach the very end of the train without ever finding a taller block, you write down a negative one instead to show that no taller block exists. You repeat this for every number in the first train until you have a whole new list of answers.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||||
| WalkCCC | C++ | Java | Python | ||||||||
| leetcode.ca | C++ | Java | Python | JS | Go | Rust | TS | ||||
| LeetcodeHelp | C++ | Java | Python | ||||||||
| Progiez | C++ | Java | Python | ||||||||
| github | BigEggStudy | C# | |||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| FelixFan1122 | C# | ||||||||||
| fengvyi | C++ | ||||||||||
| fsq | C++ | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| wisdompeak | C++ | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| FelixFan1122 | C# | ||||||||||
| fengvyi | C++ | ||||||||||
| fsq | C++ | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| wisdompeak | C++ | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 503: Next Greater Element II
- problem 556: Next Greater Element III
- problem 739: Daily Temperatures
- problem 2104: Sum of Subarray Ranges
- problem 2281: Sum of Total Strength of Wizards
- problem 2454: Next Greater Element IV
- problem 2487: Remove Nodes From Linked List
- problem 2996: Smallest Missing Integer Greater Than Sequential Prefix Sum
Solved On The Same Day
- problem 476: Number Complement
- problem 6: Zigzag Conversion
- problem 38: Count and Say
- problem 147: Insertion Sort List
- problem 148: Sort List
- problem 494: Target Sum
- problem 498: Diagonal Traverse
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality