2454. Next Greater Element IV LeetCode Solution

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.

Problem Statement
Complexity Analysis
Next Greater Element IV solution in C++
Next Greater Element IV solution in Java
Next Greater Element IV solution in Python
Additional Resources

2454. Next Greater Element IV LeetCode Solution image

Problem Statement of Next Greater Element IV

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

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