In this guide, you will get 2454. Next Greater Element IV LeetCode Solution with the best time and space complexity. The solution to Next Greater Element IV problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2454. Next Greater Element IV LeetCode Solution in C++
class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
vector<int> ans(nums.size(), -1);
// a decreasing stack that stores indices that met the first greater number
stack<int> prevStack;
// a decreasing stack that stores indices
stack<int> currStack;
for (int i = 0; i < nums.size(); ++i) {
// Indices in `prevStack` meet the second greater number.
while (!prevStack.empty() && nums[prevStack.top()] < nums[i])
ans[prevStack.top()] = nums[i], prevStack.pop();
// Push indices that meet the first greater number from `currStack` to
// `prevStack`. We need a temporary array to make the indices in the
// `prevStack` increasing.
stack<int> decreasingIndices;
while (!currStack.empty() && nums[currStack.top()] < nums[i])
decreasingIndices.push(currStack.top()), currStack.pop();
while (!decreasingIndices.empty())
prevStack.push(decreasingIndices.top()), decreasingIndices.pop();
currStack.push(i);
}
return ans;
}
}; /* code provided by PROGIEZ */
2454. Next Greater Element IV LeetCode Solution in Java
class Solution {
public int[] secondGreaterElement(int[] nums) {
int[] ans = new int[nums.length];
Arrays.fill(ans, -1);
// a decreasing stack that stores indices that met the first greater number
Deque<Integer> prevStack = new ArrayDeque<>();
// a decreasing stack that stores indices
Deque<Integer> currStack = new ArrayDeque<>();
for (int i = 0; i < nums.length; ++i) {
// Indices in prevStack meet the second greater num.
while (!prevStack.isEmpty() && nums[prevStack.peek()] < nums[i])
ans[prevStack.poll()] = nums[i];
// Push indices that meet the first greater number from `currStack` to
// `prevStack`. We need a temporary array to make the indices in the
// `prevStack` increasing.
Deque<Integer> decreasingIndices = new ArrayDeque<>();
while (!currStack.isEmpty() && nums[currStack.peek()] < nums[i])
decreasingIndices.push(currStack.poll());
while (!decreasingIndices.isEmpty())
prevStack.push(decreasingIndices.poll());
currStack.push(i);
}
return ans;
}
} // code provided by PROGIEZ
2454. Next Greater Element IV LeetCode Solution in Python
class Solution:
def secondGreaterElement(self, nums: list[int]) -> list[int]:
ans = [-1] * len(nums)
# a decreasing stack that stores indices that met the first greater number.
prevStack = []
# a decreasing stack that stores indices.
currStack = []
for i, num in enumerate(nums):
# Indices in prevStack meet the second greater num.
while prevStack and nums[prevStack[-1]] < num:
ans[prevStack.pop()] = num
# Push indices that meet the first greater number from `currStack` to
# `prevStack`. We need a temporary array to make the indices in the
# `prevStack` increasing.
decreasingIndices = []
while currStack and nums[currStack[-1]] < num:
decreasingIndices.append(currStack.pop())
while decreasingIndices:
prevStack.append(decreasingIndices.pop())
currStack.append(i)
return ans # code by PROGIEZ
