HardNo. 2454
Next Greater Element IV — LeetCode 2454 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Stack, Array, Binary Search, Sorting, Monotonic Stack, Heap (Priority Queue)
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a 0-indexed array of non-negative integers nums. For each integer in nums, you must find its respective second greater integer.
Example
- Input
- nums = [2,4,0,9,6]
- Output
- [9,6,6,-1,-1]
- Explanation
- 0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2.
Python solution
class Solution:
def secondGreaterElement(self, nums: List[int]) -> List[int]:
arr = [(x, i) for i, x in enumerate(nums)]
arr.sort(key=lambda x: -x[0])
sl = SortedList()
n = len(nums)
ans = [-1] * n
for _, i in arr:
j = sl.bisect_right(i)
if j + 1 < len(sl):
ans[i] = nums[sl[j + 1]]
sl.add(i)
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2454. Next Greater Element IV is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2736 | Maximum Sum Queries | Hard |
| 2940 | Find Building Where Alice and Bob Can Meet | Hard |
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 0456 | 132 Pattern | Medium |
| 0853 | Car Fleet | Medium |
| 1268 | Search Suggestions System | Medium |
Frequently asked questions
- How hard is LeetCode 2454. Next Greater Element IV?
LeetCode 2454. Next Greater Element IV is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2454. Next Greater Element IV?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2454. Next Greater Element IV?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2454. Next Greater Element IV cover?
LeetCode 2454. Next Greater Element IV is tagged Stack, Array, Binary Search, Sorting, Monotonic Stack and Heap (Priority Queue) on LeetCode.