#2454

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Next Greater Element IV

Find the second greater integer for each element in an array using binary search and monotonic stack techniques.

array binary search stack sorting heap priority queue

Problem Statement

You are given a 0-indexed array of non-negative integers, nums. For each integer at index i, you need to find its second greater integer in the array. A second greater integer is defined as the next integer that is greater than the current integer, but also greater than the first greater integer found to its right.

If no such integer exists for a given element, return -1 for that index. The goal is to do this efficiently given that the array can be as large as 10^5 elements, and the elements themselves can be as large as 10^9.

Examples

Example 1

Input: nums = [2,4,0,9,6]

Output: [9,6,6,-1,-1]

0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2. 1st index: 9 is the first, and 6 is the second integer greater than 4, to the right of 4. 2nd index: 9 is the first, and 6 is the second integer greater than 0, to the right of 0. 3rd index: There is no integer greater than 9 to its right, so the second greater integer is considered to be -1. 4th index: There is no integer greater than 6 to its right, so the second greater integer is considered to be -1. Thus, we return [9,6,6,-1,-1].

Example 2

Input: nums = [3,3]

Output: [-1,-1]

We return [-1,-1] since neither integer has any integer greater than it.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 109

Solution Approach

Binary Search over Valid Answer Space

Use binary search to identify a valid range for potential second greater integers. By working with the monotonic stack structure, we can efficiently track greater values and find the second greater integer in the appropriate answer space.

Monotonic Stack for First Greater Value

Traverse through the array and maintain a stack of elements in non-increasing order. For each element, look for the first greater integer by comparing with the stack's top. This helps in locating the second greater integer in a single pass.

Efficient Stack and Search Combination

Combine the use of binary search and monotonic stacks to reduce the overall time complexity. The stack efficiently tracks the largest elements to the right of a given element, and binary search narrows down the range for the second greater integer.

Complexity Analysis

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

The time complexity depends on the chosen solution approach. Using a monotonic stack ensures O(n) time for processing elements. Binary search may improve the solution's space and search efficiency, but the complexity will vary based on implementation specifics.

What Interviewers Usually Probe

Strong understanding of stack-based algorithms.
Ability to apply binary search in non-trivial spaces.
Familiarity with space and time optimization techniques for large inputs.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the case where no second greater integer exists.
Incorrectly using the stack, which could lead to missing the first or second greater integer.
Not optimizing space complexity when handling large arrays.

Follow-up variants

Modify the problem to find the first greater element instead of the second greater element.
Change the problem to find the second smallest greater element instead of the second greatest.
Adapt the problem to allow negative numbers and test for edge cases involving zero.

FAQ

What is the main algorithmic pattern in Next Greater Element IV?

The problem leverages binary search over the valid answer space combined with a monotonic stack to efficiently track and find the second greater element.

What is the time complexity of the solution?

The time complexity depends on the approach used but can range from O(n) using a monotonic stack with some binary search optimization.

How does a monotonic stack help in this problem?

A monotonic stack helps efficiently track the first greater element in the array, which is necessary for finding the second greater element in an optimized manner.

What is the space complexity of this problem?

Space complexity is typically O(n), depending on how the stack and any additional search structures are implemented.

Can you solve this problem with a brute force approach?

Yes, a brute force solution would involve checking each pair of elements to find the second greater element, but it would be inefficient with time complexity of O(n^2).

terminal

Solution

Solution 1: Sorting + Ordered Set

We can convert the elements in the array into pairs $(x, i)$, where $x$ is the value of the element and $i$ is the index of the element. Then sort by the value of the elements in descending order.

1

2

3

4

5

6

7

8

9

10

11

12

13

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 ans

Continue Practicing

#2617 minimum number of visited cells in a grid #2818 apply operations to maximize score #1996 the number of weak characters in the game