Next Greater Element IV

HARD

Description

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.

The second greater integer of nums[i] is nums[j] such that:

j > i
nums[j] > nums[i]
There exists exactly one index k such that nums[k] > nums[i] and i < k < j.

If there is no such nums[j], the second greater integer is considered to be -1.

For example, in the array [1, 2, 4, 3], the second greater integer of 1 is 4, 2 is 3, and that of 3 and 4 is -1.

Return an integer array answer, where answer[i] is the second greater integer of nums[i].

Example 1:

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.
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]
Explanation:
We return [-1,-1] since neither integer has any integer greater than it.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Approaches

Checkout 3 different approaches to solve Next Greater Element IV. Click on different approaches to view the approach and algorithm in detail.

Optimal Solution with Two Monotonic Stacks

This is the most efficient approach, achieving linear time complexity. It builds upon the idea of using a monotonic stack but employs a second stack instead of a priority queue to manage elements that are waiting for their second greater element. This avoids the logarithmic time complexity of priority queue operations.

Algorithm

Initialize answer array of size n with -1.
Initialize two stacks, s1 and s2, to store indices.
For i from 0 to n-1:
Let currentNum = nums[i].
While s2 is not empty and nums[s2.peek()] < currentNum:
```
`answer[s2.pop()] = currentNum`.
```
Initialize a temporary stack temp.
While s1 is not empty and nums[s1.peek()] < currentNum:
```
`temp.push(s1.pop())`.
```
While temp is not empty:
s2.push(temp.pop()).
Push i onto s1.
Return answer.

We use two stacks, s1 and s2. Both will store indices and will be maintained as monotonic stacks (elements with smaller values on top of elements with larger values).

s1: Stores indices of elements for which we are looking for the first greater element.
s2: Stores indices of elements for which we have found the first greater element and are now looking for the second. We iterate through the array nums with index i. For each nums[i]:

We first process s2. While s2 is not empty and the element at its top nums[s2.peek()] is smaller than nums[i], we have found the second greater element for s2.peek(). We pop the index and set its answer to nums[i].
Then, we process s1. While s1 is not empty and nums[s1.peek()] is smaller than nums[i], we have found the first greater element. We pop these indices from s1. Since they now need to find their second greater element, they must be moved to s2.
A crucial detail is how to move elements from s1 to s2. When we pop multiple indices from s1, they come out in increasing order of their corresponding values. To maintain s2 as a monotonic (decreasing value) stack, we must push these indices onto s2 in reverse order. We can use a temporary stack to achieve this reversal.
Finally, we push the current index i onto s1. This single pass through the array correctly identifies the second greater element for all indices in linear time.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        Arrays.fill(answer, -1);

        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<Integer> s2 = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            int currentNum = nums[i];

            while (!s2.isEmpty() && nums[s2.peek()] < currentNum) {
                answer[s2.pop()] = currentNum;
            }

            Deque<Integer> tempStack = new ArrayDeque<>();
            while (!s1.isEmpty() && nums[s1.peek()] < currentNum) {
                tempStack.push(s1.pop());
            }
            while(!tempStack.isEmpty()){
                s2.push(tempStack.pop());
            }

            s1.push(i);
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: O(N). Each index is pushed and popped from `s1`, `temp`, and `s2` at most once. All operations are amortized O(1), leading to a total linear time complexity.Space Complexity: O(N). In the worst case (e.g., a strictly decreasing array), all indices could be stored in the stacks.

Pros and Cons

Pros:

Optimal time complexity. It's the most efficient way to solve this problem.

Cons:

The logic involving three stacks (including the temporary one) can be slightly more complex to reason about compared to the priority queue approach.

Code Solutions

Checking out 3 solutions in different languages for Next Greater Element IV. Click on different languages to view the code.

class Solution {
public
  int[] secondGreaterElement(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    int[][] arr = new int[n][0];
    for (int i = 0; i < n; ++i) {
      arr[i] = new int[]{nums[i], i};
    }
    Arrays.sort(arr, (a, b)->a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
    TreeSet<Integer> ts = new TreeSet<>();
    for (int[] pair : arr) {
      int i = pair[1];
      Integer j = ts.higher(i);
      if (j != null && ts.higher(j) != null) {
        ans[i] = nums[ts.higher(j)];
      }
      ts.add(i);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Next Greater Element IV

Algorithms:

Binary SearchSorting

Data Structures:

ArrayStackHeap (Priority Queue)Monotonic Stack