Problem

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 arrayanswer , whereanswer[i]is the second greater integer ofnums[i].

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4

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^5
  • 0 <= nums[i] <= 10^9

Solution

Method 1 -

Intuition

We need to find, for each element, the second greater element to its right. This is a monotonic stack problem, but we need to track two levels of “greater”. We can use two stacks: one for first greater, one for second greater.

Approach

Iterate through the array. For each index, use two stacks:

  1. The first stack tracks indices waiting for their first greater.
  2. The second stack tracks indices waiting for their second greater. When a new value is greater than the top of the first stack, move those indices to the second stack. When a new value is greater than the top of the second stack, set answer for those indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

vector<int> secondGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st1, st2;
    vector<int> wait;
    for (int i = 0; i < n; ++i) {
        while (!st2.empty() && nums[i] > nums[st2.top()]) {
            res[st2.top()] = nums[i]; st2.pop();
        }
        wait.clear();
        while (!st1.empty() && nums[i] > nums[st1.top()]) {
            wait.push_back(st1.top()); st1.pop();
        }
        for (int j = wait.size()-1; j >= 0; --j) st2.push(wait[j]);
        st1.push(i);
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func secondGreater(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res { res[i] = -1 }
    st1, st2 := []int{}, []int{}
    for i := 0; i < n; i++ {
        for len(st2) > 0 && nums[i] > nums[st2[len(st2)-1]] {
            res[st2[len(st2)-1]] = nums[i]
            st2 = st2[:len(st2)-1]
        }
        wait := []int{}
        for len(st1) > 0 && nums[i] > nums[st1[len(st1)-1]] {
            wait = append(wait, st1[len(st1)-1])
            st1 = st1[:len(st1)-1]
        }
        for j := len(wait)-1; j >= 0; j-- {
            st2 = append(st2, wait[j])
        }
        st1 = append(st1, i)
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int[] secondGreater(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> st1 = new ArrayDeque<>(), st2 = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st2.isEmpty() && nums[i] > nums[st2.peekLast()]) {
            res[st2.pollLast()] = nums[i];
        }
        List<Integer> wait = new ArrayList<>();
        while (!st1.isEmpty() && nums[i] > nums[st1.peekLast()]) {
            wait.add(st1.pollLast());
        }
        for (int j = wait.size()-1; j >= 0; j--) st2.addLast(wait.get(j));
        st1.addLast(i);
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fun secondGreater(nums: IntArray): IntArray {
    val n = nums.size
    val res = IntArray(n) { -1 }
    val st1 = ArrayDeque<Int>()
    val st2 = ArrayDeque<Int>()
    for (i in 0 until n) {
        while (st2.isNotEmpty() && nums[i] > nums[st2.last()]) {
            res[st2.removeLast()] = nums[i]
        }
        val wait = mutableListOf<Int>()
        while (st1.isNotEmpty() && nums[i] > nums[st1.last()]) {
            wait.add(st1.removeLast())
        }
        for (j in wait.size-1 downTo 0) st2.addLast(wait[j])
        st1.addLast(i)
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def secondGreater(nums):
    n = len(nums)
    res = [-1] * n
    st1, st2 = [], []
    for i, v in enumerate(nums):
        while st2 and v > nums[st2[-1]]:
            res[st2.pop()] = v
        wait = []
        while st1 and v > nums[st1[-1]]:
            wait.append(st1.pop())
        for j in reversed(wait):
            st2.append(j)
        st1.append(i)
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn second_greater(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut res = vec![-1; n];
        let mut st1 = Vec::new();
        let mut st2 = Vec::new();
        for i in 0..n {
            while let Some(&j) = st2.last() {
                if nums[i] > nums[j] {
                    res[j] = nums[i];
                    st2.pop();
                } else { break; }
            }
            let mut wait = Vec::new();
            while let Some(&j) = st1.last() {
                if nums[i] > nums[j] {
                    wait.push(j);
                    st1.pop();
                } else { break; }
            }
            for &j in wait.iter().rev() { st2.push(j); }
            st1.push(i);
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

function secondGreater(nums: number[]): number[] {
    const n = nums.length;
    const res = Array(n).fill(-1);
    const st1: number[] = [], st2: number[] = [];
    for (let i = 0; i < n; i++) {
        while (st2.length && nums[i] > nums[st2[st2.length-1]]) {
            res[st2.pop()!] = nums[i];
        }
        const wait: number[] = [];
        while (st1.length && nums[i] > nums[st1[st1.length-1]]) {
            wait.push(st1.pop()!);
        }
        for (let j = wait.length-1; j >= 0; j--) st2.push(wait[j]);
        st1.push(i);
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of nums.
  • 🧺 Space complexity: O(n) for stacks and result.