Next Greater Element IV

Hard
1402.

Next Greater Element IV

Next Greater Element IV is a hard coding problem on arrays, sorting and stack, asked in Amazon, Google and Bloomberg interviews.

For every index i of nums, find its second greater element: scanning to the right of i, ignore elements that are not strictly greater than nums[i]; the second strictly greater element you meet is the answer.

Formally it is nums[j] for the smallest j > i with nums[j] > nums[i] such that exactly one index k with i < k < j also has nums[k] > nums[i]. If no such j exists the answer is -1.

Return the array of answers.

Example 1

Input
nums = [1,5,2,4,3]
Output
[2,-1,3,-1,-1]
Explanation
For 1 the greater elements to its right are 5, 2, 4, 3 — the second is 2. For 2 they are 4 and 3, so the answer is 3.

Example 2

Input
nums = [6,1,8,3,9]
Output
[9,3,-1,-1,-1]

Example 3

Input
nums = [4,4,4]
Output
[-1,-1,-1]
Explanation
Equal values are not greater.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var secondGreaterElement = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Next Greater Element IV — Solution in Python, Java & C++

Next Greater Element IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Next Greater Element IV is a hard coding problem on arrays, sorting and stack, asked in Amazon, Google and Bloomberg interviews.

Problem statement

For every index i of nums, find its second greater element: scanning to the right of i, ignore elements that are not strictly greater than nums[i]; the second strictly greater element you meet is the answer.

Formally it is nums[j] for the smallest j > i with nums[j] > nums[i] such that exactly one index k with i < k < j also has nums[k] > nums[i]. If no such j exists the answer is -1.

Return the array of answers.

Example 1

Input: nums = [1,5,2,4,3]
Output: [2,-1,3,-1,-1]
Explanation: For 1 the greater elements to its right are 5, 2, 4, 3 — the second is 2. For 2 they are 4 and 3, so the answer is 3.

Example 2

Input: nums = [6,1,8,3,9]
Output: [9,3,-1,-1,-1]

Example 3

Input: nums = [4,4,4]
Output: [-1,-1,-1]
Explanation: Equal values are not greater.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

Hints for Next Greater Element IV

  1. Hint 1

    The classic next-greater stack answers 'first greater'. What happens to an index at the moment its first greater element arrives?

  2. Hint 2

    Once an index has seen one greater element, it is waiting for a second one — keep those indices in a second stack.

  3. Hint 3

    For each new value: first settle indices of the second stack smaller than it, then move indices of the first stack smaller than it onto the second stack (keeping their order), then push the new index onto the first stack.

How to solve Next Greater Element IV

Track every index in one of two monotonic stacks: first holds indices that have not met any greater element yet, second holds indices that have met exactly one. A new value finishes some indices of second and promotes some of first.

Approach

  1. Fill ans with -1; keep two stacks of indices, first and second, each with non-increasing values from bottom to top.
  2. For index i with value x, pop from second while its top value is < x and set their answer to x — this is their second greater element.
  3. Pop from first while its top value is < x into a temporary list — x is their first greater element.
  4. Push the temporary list onto second in reverse order of popping (largest value first), so second stays monotonic.
  5. Push i onto first.

Why it works

An index moves first → second → done exactly when it meets its first and second strictly greater elements, because each stack is sorted: everything smaller than x sits at the top, so the pops touch exactly the indices that x exceeds. Settling second before promoting from first matters — an index promoted by x must not be finished by the same x. The promoted values are all < x <= everything left in second, so pushing them largest first keeps second monotonic.

Complexity

  • Time — O(n) — each index is pushed and popped at most twice
  • Space — O(n)

Pitfalls

  • Process the second stack first; otherwise an index would count the same element as both its first and second greater.
  • Keep the moved indices in order — appending them reversed breaks the monotonic invariant of second.
  • Strictly greater: equal values never count.

Reference solution

Python

from typing import List

def secondGreaterElement(nums: List[int]) -> List[int]:
    ans = [-1] * len(nums)
    first = []
    second = []
    for i, x in enumerate(nums):
        while second and nums[second[-1]] < x:
            ans[second.pop()] = x
        moved = []
        while first and nums[first[-1]] < x:
            moved.append(first.pop())
        second.extend(reversed(moved))
        first.append(i)
    return ans

Java

public static int[] secondGreaterElement(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    int[] first = new int[n], second = new int[n], moved = new int[n];
    int f = 0, s = 0;
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        while (s > 0 && nums[second[s - 1]] < x) ans[second[--s]] = x;
        int m = 0;
        while (f > 0 && nums[first[f - 1]] < x) moved[m++] = first[--f];
        for (int k = m - 1; k >= 0; k--) second[s++] = moved[k];
        first[f++] = i;
    }
    return ans;
}

C++

vector<int> secondGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1), first, second, moved;
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        while (!second.empty() && nums[second.back()] < x) {
            ans[second.back()] = x;
            second.pop_back();
        }
        moved.clear();
        while (!first.empty() && nums[first.back()] < x) {
            moved.push_back(first.back());
            first.pop_back();
        }
        for (int k = (int)moved.size() - 1; k >= 0; k--) second.push_back(moved[k]);
        first.push_back(i);
    }
    return ans;
}

JavaScript

var secondGreaterElement = function(nums) {
    var n = nums.length;
    var ans = new Array(n).fill(-1);
    var first = [], second = [];
    for (var i = 0; i < n; i++) {
        var x = nums[i];
        while (second.length > 0 && nums[second[second.length - 1]] < x) ans[second.pop()] = x;
        var moved = [];
        while (first.length > 0 && nums[first[first.length - 1]] < x) moved.push(first.pop());
        for (var k = moved.length - 1; k >= 0; k--) second.push(moved[k]);
        first.push(i);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms