Next Greater Element IV

Problem 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].

Key Insights

• The problem requires finding the second greater element while adhering to specific conditions regarding indices and values.
• A monotonic stack can efficiently track elements and their indices to determine the greater elements in a single pass.
• The constraints indicate that an O(n) solution is necessary due to the potential size of the input.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a monotonic stack to keep track of the indices of the elements in nums. We will iterate through the array, and for each element, we will check if we can find the first greater and then the second greater element using the stack. The stack will help us maintain the indices of elements in a way that allows us to efficiently find the required greater elements.

1. Initialize a stack to keep track of indices of elements.
2. Create an output array initialized with -1.
3. Traverse the nums array from right to left:
   • For each element, pop elements from the stack that are less than or equal to the current element.
   • If the stack is not empty, the top of the stack gives the next greater element.
   • If the stack has more than one element after popping, the second element gives the second greater element.
4. Push the current index onto the stack.
5. Return the output array.

Code Solutions