LeetCode in Kotlin

2454. Next Greater Element IV

Hard

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

Solution

import java.util.ArrayDeque
import java.util.Deque

class Solution {
    fun secondGreaterElement(nums: IntArray): IntArray {
        val res = IntArray(nums.size)
        res.fill(-1)
        val stack1: Deque<Int> = ArrayDeque()
        val stack2: Deque<Int> = ArrayDeque()
        val tmp: Deque<Int> = ArrayDeque()
        for (i in nums.indices) {
            while (stack2.isNotEmpty() && nums[i] > nums[stack2.peek()]) {
                res[stack2.pop()] = nums[i]
            }
            while (stack1.isNotEmpty() && nums[i] > nums[stack1.peek()]) {
                tmp.push(stack1.pop())
            }
            while (tmp.isNotEmpty()) {
                stack2.push(tmp.pop())
            }
            stack1.push(i)
        }
        return res
    }
}

This site is open source. Improve this page.