Practice/DoorDash/Leetcode 2454. Next Greater Element IV

Leetcode 2454. Next Greater Element IV

CodingOptional

Problem

Given an array of integers nums, for each element find the second element to its right that is strictly greater than it. More specifically, for each position i, you need to:

1. Find the first element to the right of nums[i] that is strictly greater than nums[i]
2. Then find the next element to the right that is strictly greater than nums[i] (not necessarily greater than the first one found)

Return an array where each position contains the second strictly greater element for the corresponding position in the input array. If no such element exists, use -1 for that position.

Requirements

1. Return an array of the same length as the input
2. For each element, find the second occurrence of a strictly greater element to its right
3. Elements must be to the right (higher indices) of the current element
4. Return -1 if fewer than two strictly greater elements exist to the right
5. Handle edge cases including single elements and decreasing sequences

Constraints

• 1 <= nums.length <= 100,000
• 0 <= nums[i] <= 1,000,000,000
• Expected time complexity: O(n)
• Expected space complexity: O(n)

Examples

Example 1:

` Input: nums = [2, 4, 0, 9, 6] Output: [9, 6, 6, -1, -1] Explanation:

• For index 0 (value 2): First greater is 4 at index 1, second greater is 9 at index 3
• For index 1 (value 4): First greater is 9 at index 3, second greater is 6 at index 4
• For index 2 (value 0): First greater is 9 at index 3, second greater is 6 at index 4
• For index 3 (value 9): No greater elements exist to the right
• For index 4 (value 6): No greater elements exist to the right `

Example 2:

Input: nums = [5, 4, 3, 2, 1] Output: [-1, -1, -1, -1, -1] Explanation: The array is strictly decreasing, so no element has any greater element to its right.

Example 3:

` Input: nums = [1, 5, 2, 7, 3, 8] Output: [7, 8, 8, -1, 8, -1] Explanation:

• For 1: greater elements are 5 and 7 (second is 7)
• For 5: greater elements are 7 and 8 (second is 8)
• For 2: greater elements are 7 and 8 (second is 8)
• For 7: only one greater element (8) exists
• For 3: greater elements are 8 (only one, but we need to count carefully - 8 is greater, then no more)
• For 8: no greater elements `