Skip to main content
Talentd

Next Greater Element IV - Solution & Explanation

HardArrayBinary SearchStackSorting27 min readAsked at: Meta
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array nums. For each index i, find the second element to the right that is strictly greater than nums[i]. The first greater element is ignored; the answer must be the next greater element that appears after it. If such an element does not exist, return -1 for that position.

Approach 1: Stack-Based Approach (Monotonic Stack) (Time: O(n), Space: O(n))

This approach processes the array from left to right while maintaining two stacks of indices. The first stack tracks elements waiting for their first greater value using a decreasing monotonic stack. When a larger number appears, indices popped from this stack have found their first greater element and move to a second stack. The second stack holds indices that are now waiting for their second greater value.

Whenever the current number is larger than the values represented by indices in the second stack, those elements have found their second greater element and can be resolved immediately. Each index moves through the stacks at most once, so the algorithm runs in linear time. This technique combines ideas from stack processing and array traversal to efficiently track both first and second greater relationships.

Approach 2: Priority Queue (Heap) Approach (Time: O(n log n), Space: O(n))

This approach separates the discovery of the first greater element from the search for the second greater element using a min-heap. While scanning the array, maintain a monotonic stack to identify when an element finds its first greater value. Once that happens, push the index into a priority queue (min-heap) keyed by its value.

As you continue iterating, compare the current value with the smallest values in the heap. If the current number is greater, it becomes the second greater element for those indices, and they are removed from the heap. Heap operations introduce a log n factor, making the complexity O(n log n), but the implementation is often easier to reason about when separating the two phases.

Recommended for interviews: The stack-based monotonic approach is typically expected in interviews because it achieves optimal O(n) time and demonstrates strong understanding of monotonic stack patterns. The heap approach is still valid and easier to derive, but the extra log n factor makes it slightly less optimal.

Approach 1: Stack-Based Approach

This approach involves using two stacks to maintain indices related to the next greater element. First, find the first greater element for each position with the help of a monotonic stack. Then use another pass to determine the second greater element by utilizing the previously built information.

This implementation uses two stacks. As we traverse the array from the end:
1. If an element is greater than the current `i` element, it is pushed to the first stack.
2. For every element processed, its second greater element is popped from the second stack if it exists.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input array. We perform a constant amount of work per element.
Space Complexity: O(n), due to the storage requirements of the stacks used.

Try this approach in the editor →

Approach 2: Priority Queue (Heap) Approach

Another approach is to use a min-heap (priority queue) to find the second greater element. By iterating from the start and maintaining order in a heap, you can effectively emulate the stack operations by priority ordering.

In this C implementation, we simulate the behavior of a min-heap. The array `heap` is restructured as needed to maintain the heap property. Each insertion involves heapify operation to maintain the max heap order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), where n is the size of input array due to heap operations. Space Complexity: O(n) from heap usage.

Try this approach in the editor →

Approach 3: Sorting + Ordered Set

We can convert the elements in the array into pairs (x, i), where x is the value of the element and i is the index of the element. Then sort by the value of the elements in descending order.

Next, we traverse the sorted array, maintaining an ordered set that stores the indices of the elements. When we traverse to the element (x, i), the indices of all elements greater than x are already in the ordered set. We only need to find the index j of the next element after i in the ordered set, then the element corresponding to j is the second largest element of x. Then, we add i to the ordered set. Continue to traverse the next element.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array.

Code

PythonJavaC++TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-Based Approach

Time Complexity: O(n), where n is the length of the input array. We perform a constant amount of work per element.
Space Complexity: O(n), due to the storage requirements of the stacks used.

Priority Queue (Heap) Approach

Time Complexity: O(n log n), where n is the size of input array due to heap operations. Space Complexity: O(n) from heap usage.

Sorting + Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Monotonic StacksO(n)O(n)Best general solution; optimal linear scan using stack transitions
Stack + Priority Queue (Heap)O(n log n)O(n)Easier conceptual separation between first and second greater discovery

Video Solution

2454. Next Greater Element IV | Leetcode BiWeekly 90 | LeetCode 2454 • Bro Coders • 4,957 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Next Greater Element IV easy or hard?
Next Greater Element IV is classified as a Hard problem because it extends the standard next-greater-element pattern to track two sequential greater elements. Solving it efficiently requires careful stack transitions and understanding of monotonic stack behavior.
How to solve Next Greater Element IV in O(n)?
Scan the array once while maintaining two stacks. The first stack tracks indices waiting for their first greater element, and the second stack tracks indices waiting for their second greater element. When a larger number appears, move indices from the first stack to the second and resolve answers for indices in the second stack.
What is the best approach for Next Greater Element IV?
The optimal approach uses two monotonic stacks to track elements waiting for their first and second greater values. Each index moves between stacks at most once, giving O(n) time and O(n) space complexity. This method is commonly expected in technical interviews because it extends the classic Next Greater Element pattern.
What data structure is used in Next Greater Element IV?
The main data structure is a monotonic stack, which efficiently tracks elements waiting for a greater value. Some implementations also use a priority queue (min-heap) to manage candidates waiting for their second greater element.
What is the time complexity of Next Greater Element IV?
The optimal stack-based solution runs in O(n) time because each element is pushed and popped from the stacks at most once. A heap-based alternative runs in O(n log n) time due to priority queue operations. Both approaches use O(n) extra space for stacks or heaps.
Next Greater Element IV Python or Java solution approach?
In Python or Java, the recommended solution uses two stacks to track indices. Iterate through the array, resolve second greater elements from the second stack, move indices from the first stack when their first greater element appears, and push the current index to the first stack.
Is Next Greater Element IV asked at Google, Amazon, or Meta?
Variations of the Next Greater Element pattern frequently appear in interviews at companies like Google, Amazon, and Meta. Harder versions such as Next Greater Element IV test deeper understanding of monotonic stacks and multi-stage element tracking.

Ready to solve this problem?

Practice Next Greater Element IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Apply Operations to Maximize Score

Next

Next Greater Element I