Next Greater Element IV

Problem#

For each index i, return the second strictly greater element to the right — i.e., the value at j where j is the smallest index such that there exist at least two indices k > i with nums[k] > nums[i] and j is the second such index. Return -1 if no such element exists.

Examples#

nums = [2,4,0,9,6] → [9,6,6,-1,-1]
nums = [3,3] → [-1,-1]

Constraints#

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

Approach#

Use two monotonic decreasing stacks. Stack s1 finds first-next-greater as usual. When s1 pops an index, instead of finalizing, move it to a holding buffer. Stack s2 is checked first: anything popped from s2 is the second-next-greater. To preserve ordering on s2, drain s1 popped elements in increasing order of value (i.e., bottom up) before merging.

Solution#

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> s1, s2;
        for (int i = 0; i < n; ++i) {
            while (!s2.empty() && nums[s2.top()] < nums[i]) {
                ans[s2.top()] = nums[i];
                s2.pop();
            }
            stack<int> tmp;
            while (!s1.empty() && nums[s1.top()] < nums[i]) {
                tmp.push(s1.top());
                s1.pop();
            }
            while (!tmp.empty()) {
                s2.push(tmp.top());
                tmp.pop();
            }
            s1.push(i);
        }
        return ans;
    }
};

func secondGreaterElement(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    s1, s2 := []int{}, []int{}
    for i := 0; i < n; i++ {
        for len(s2) > 0 && nums[s2[len(s2)-1]] < nums[i] {
            ans[s2[len(s2)-1]] = nums[i]
            s2 = s2[:len(s2)-1]
        }
        tmp := []int{}
        for len(s1) > 0 && nums[s1[len(s1)-1]] < nums[i] {
            tmp = append(tmp, s1[len(s1)-1])
            s1 = s1[:len(s1)-1]
        }
        for j := len(tmp) - 1; j >= 0; j-- {
            s2 = append(s2, tmp[j])
        }
        s1 = append(s1, i)
    }
    return ans
}

from typing import List

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        s1: list[int] = []
        s2: list[int] = []
        for i in range(n):
            while s2 and nums[s2[-1]] < nums[i]:
                ans[s2.pop()] = nums[i]
            tmp: list[int] = []
            while s1 and nums[s1[-1]] < nums[i]:
                tmp.append(s1.pop())
            for j in range(len(tmp) - 1, -1, -1):
                s2.append(tmp[j])
            s1.append(i)
        return ans

function secondGreaterElement(nums) {
    const n = nums.length;
    const ans = new Array(n).fill(-1);
    const s1 = [], s2 = [];
    for (let i = 0; i < n; i++) {
        while (s2.length && nums[s2[s2.length - 1]] < nums[i]) {
            ans[s2.pop()] = nums[i];
        }
        const tmp = [];
        while (s1.length && nums[s1[s1.length - 1]] < nums[i]) {
            tmp.push(s1.pop());
        }
        for (let j = tmp.length - 1; j >= 0; j--) {
            s2.push(tmp[j]);
        }
        s1.push(i);
    }
    return ans;
}

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<Integer> s2 = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!s2.isEmpty() && nums[s2.peek()] < nums[i]) {
                ans[s2.pop()] = nums[i];
            }
            Deque<Integer> tmp = new ArrayDeque<>();
            while (!s1.isEmpty() && nums[s1.peek()] < nums[i]) {
                tmp.push(s1.pop());
            }
            while (!tmp.isEmpty()) {
                s2.push(tmp.pop());
            }
            s1.push(i);
        }
        return ans;
    }
}

function secondGreaterElement(nums: number[]): number[] {
    const n = nums.length;
    const ans: number[] = new Array(n).fill(-1);
    const s1: number[] = [];
    const s2: number[] = [];
    for (let i = 0; i < n; i++) {
        while (s2.length && nums[s2[s2.length - 1]] < nums[i]) {
            ans[s2.pop()!] = nums[i];
        }
        const tmp: number[] = [];
        while (s1.length && nums[s1[s1.length - 1]] < nums[i]) {
            tmp.push(s1.pop()!);
        }
        for (let j = tmp.length - 1; j >= 0; j--) {
            s2.push(tmp[j]);
        }
        s1.push(i);
    }
    return ans;
}

Editorial#

s1 is the standard monotone-decreasing stack for “next greater”. Whatever s1 pops at index i has already encountered its first greater (which is nums[i]). Those popped indices are still candidates for “second greater”, so they migrate to s2. The transfer preserves the decreasing order using a temporary buffer, which keeps s2 monotonic and amortized linear overall.

Complexity#

Time: O(n).
Space: O(n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#