Scale Engineer

Next Greater Element IV

Hard
#2238Time: 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: O(N). In the worst case (e.g., a strictly decreasing array), all indices could be stored in the stacks.
Algorithms
Binary SearchSorting
Data structures
ArrayStackHeap (Priority Queue)Monotonic Stack

Prompt

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 <= 105
  • 0 <= nums[i] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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]:
  1. 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].
  2. 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.
  3. 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.
  4. 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

Time

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

O(N). In the worst case (e.g., a strictly decreasing array), all indices could be stored in the stacks.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem