2454. Next Greater Element IV

Description

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

 

Solutions

Solution: Stack

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const secondGreaterElement = function (nums) {
  const n = nums.length;
  const prevStack = [];
  const currentStack = [];
  const result = Array.from({ length: n }, () => -1);

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    while (prevStack.length && nums[prevStack.at(-1)] < num) {
      const pos = prevStack.pop();

      result[pos] = num;
    }

    const decIndices = [];

    while (currentStack.length && nums[currentStack.at(-1)] < num) {
      const pos = currentStack.pop();

      decIndices.push(pos);
    }

    while (decIndices.length) {
      const pos = decIndices.pop();

      prevStack.push(pos);
    }

    currentStack.push(index);
  }

  return result;
};