2454. Next Greater Element IV

HardStackArrayBinary SearchSortingMonotonic StackHeap (Priority Queue)

Problem Description

You are given a 0-indexed array of non-negative integers nums. Your task is to find the second greater integer for each element in the array.

For an element nums[i], its second greater integer is defined as nums[j] where:

j > i (the element must come after nums[i] in the array)
nums[j] > nums[i] (the element must be greater than nums[i])
There exists exactly one index k such that i < k < j and nums[k] > nums[i] (there must be exactly one element between them that is also greater than nums[i])

In other words, nums[j] is the second element to the right of nums[i] that is greater than nums[i].

If no such second greater element exists for nums[i], the result should be -1.

Example: For the array [1, 2, 4, 3]:

For 1 (index 0): The first greater element is 2 at index 1, and the second greater element is 4 at index 2. Result: 4
For 2 (index 1): The first greater element is 4 at index 2, and the second greater element is 3 at index 3. Result: 3
For 4 (index 2): There are no greater elements to its right. Result: -1
For 3 (index 3): There are no elements to its right. Result: -1

The function should return an integer array answer where answer[i] represents the second greater integer of nums[i].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is to process elements from largest to smallest. Why? Because when we're looking for the "second greater" element for any value, we only care about elements that are greater than it. By processing from largest to smallest, we ensure that when we reach an element, all larger elements have already been processed.

Think about it this way: if we're at element x, we know that all elements greater than x have already been seen. Now we need to find which of these greater elements appears as the second one after x's position in the original array.

Here's where the ordered set becomes crucial. As we process each element, we maintain an ordered set of indices of all elements we've seen so far (which are all greater than or equal to the current element). For the current element at index i, we need to find indices in our set that are greater than i (elements that appear after position i).

Using binary search (bisect_right(i)), we can quickly find the position in the ordered set where i would be inserted. This gives us the count of indices greater than i. If there are at least two such indices (meaning j + 1 < len(sl)), then the element at the second index (sl[j + 1]) corresponds to our answer - it's the second element after position i that has a value greater than nums[i].

The beauty of this approach is that by processing elements in descending order of their values, we naturally filter out smaller elements. When we're looking for the second greater element of nums[i], the ordered set only contains indices of elements with values ≥ nums[i], and we just need to find the second index that comes after i in the original array order.

Learn more about Stack, Binary Search, Sorting, Monotonic Stack and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a sorting-based approach with an ordered set to efficiently find the second greater element for each position.

Step 1: Create and Sort Pairs

arr = [(x, i) for i, x in enumerate(nums)]
arr.sort(key=lambda x: -x[0])

We create pairs of (value, index) for each element and sort them in descending order by value. This ensures we process larger elements first.

Step 2: Initialize Data Structures

sl = SortedList()
ans = [-1] * n

SortedList maintains indices in sorted order as we process elements
ans array is initialized with -1 (default when no second greater element exists)

Step 3: Process Elements from Largest to Smallest

for _, i in arr:
    j = sl.bisect_right(i)
    if j + 1 < len(sl):
        ans[i] = nums[sl[j + 1]]
    sl.add(i)

For each element at original index i:

Find position in sorted list: sl.bisect_right(i) returns the position where i would be inserted to maintain sorted order. This gives us the count of indices already in the set that are greater than i.
Check for second greater: If j + 1 < len(sl), it means there are at least two indices in the set that are greater than i. The element at sl[j + 1] is the second index after i in the original array.
Update answer: Set ans[i] = nums[sl[j + 1]] to record the second greater element.
Add current index: Add i to the sorted list for processing future elements.

Why This Works: When processing an element with value x at index i, the sorted list contains indices of all elements with values ≥ x (since we process in descending order). Among these indices, we need exactly the second one that appears after position i in the original array. The bisect_right operation efficiently finds where i fits in the sorted order of indices, and sl[j + 1] gives us the second index greater than i.

Time Complexity: O(n log n) for sorting and O(n log n) for n insertions and binary searches in the sorted list. Space Complexity: O(n) for the additional data structures.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the array [2, 4, 0, 9, 6] step by step.

Initial Setup:

Create pairs: [(2,0), (4,1), (0,2), (9,3), (6,4)]
Sort by value (descending): [(9,3), (6,4), (4,1), (2,0), (0,2)]
Initialize: sl = [], ans = [-1, -1, -1, -1, -1]

Processing each element (from largest to smallest):

Step 1: Process (9, 3) - value 9 at index 3

sl.bisect_right(3) = 0 (no indices > 3 in sl yet)
Since 0 + 1 = 1 is not < 0, no second greater element
Add 3 to sl: sl = [3]
ans = [-1, -1, -1, -1, -1]

Step 2: Process (6, 4) - value 6 at index 4

sl.bisect_right(4) = 1 (all indices in sl are ≤ 4)
Since 1 + 1 = 2 is not < 1, no second greater element
Add 4 to sl: sl = [3, 4]
ans = [-1, -1, -1, -1, -1]

Step 3: Process (4, 1) - value 4 at index 1

sl.bisect_right(1) = 0 (indices 3 and 4 are both > 1)
Since 0 + 1 = 1 < 2, we have a second greater element!
ans[1] = nums[sl[1]] = nums[4] = 6
Add 1 to sl: sl = [1, 3, 4]
ans = [-1, 6, -1, -1, -1]

Step 4: Process (2, 0) - value 2 at index 0

sl.bisect_right(0) = 0 (indices 1, 3, 4 are all > 0)
Since 0 + 1 = 1 < 3, we have a second greater element!
ans[0] = nums[sl[1]] = nums[3] = 9
Add 0 to sl: sl = [0, 1, 3, 4]
ans = [9, 6, -1, -1, -1]

Step 5: Process (0, 2) - value 0 at index 2

sl.bisect_right(2) = 2 (indices 3 and 4 are > 2)
Since 2 + 1 = 3 < 4, we have a second greater element!
ans[2] = nums[sl[3]] = nums[4] = 6
Add 2 to sl: sl = [0, 1, 2, 3, 4]
ans = [9, 6, 6, -1, -1]

Final Result: [9, 6, 6, -1, -1]

Verification:

For nums[0]=2: Greater elements to the right are 4(index 1), 9(index 3), 6(index 4). The second one is 9. ✓
For nums[1]=4: Greater elements to the right are 9(index 3), 6(index 4). The second one is 6. ✓
For nums[2]=0: Greater elements to the right are 9(index 3), 6(index 4). The second one is 6. ✓
For nums[3]=9: No greater elements exist. Result is -1. ✓
For nums[4]=6: No elements to the right. Result is -1. ✓

Solution Implementation

1from sortedcontainers import SortedList
2from typing import List
3
4class Solution:
5    def secondGreaterElement(self, nums: List[int]) -> List[int]:
6        # Create pairs of (value, index) for sorting
7        value_index_pairs = [(value, index) for index, value in enumerate(nums)]
8      
9        # Sort pairs by value in descending order (largest first)
10        value_index_pairs.sort(key=lambda pair: -pair[0])
11      
12        # SortedList to maintain indices of processed elements in sorted order
13        processed_indices = SortedList()
14      
15        # Initialize result array with -1 (default when no second greater element exists)
16        n = len(nums)
17        result = [-1] * n
18      
19        # Process elements from largest to smallest value
20        for value, current_index in value_index_pairs:
21            # Find position where current_index would be inserted (indices greater than current_index)
22            position = processed_indices.bisect_right(current_index)
23          
24            # Check if there are at least 2 elements to the right of current_index
25            if position + 1 < len(processed_indices):
26                # The element at position+1 is the second element to the right
27                second_greater_index = processed_indices[position + 1]
28                result[current_index] = nums[second_greater_index]
29          
30            # Add current index to the sorted list for future iterations
31            processed_indices.add(current_index)
32      
33        return result
34

1class Solution {
2    public int[] secondGreaterElement(int[] nums) {
3        int n = nums.length;
4      
5        // Initialize result array with -1 (default when no second greater element exists)
6        int[] result = new int[n];
7        Arrays.fill(result, -1);
8      
9        // Create array of [value, index] pairs for sorting
10        int[][] valueIndexPairs = new int[n][2];
11        for (int i = 0; i < n; i++) {
12            valueIndexPairs[i] = new int[] {nums[i], i};
13        }
14      
15        // Sort pairs by value in descending order, if values are equal then by index in ascending order
16        Arrays.sort(valueIndexPairs, (a, b) -> {
17            if (a[0] == b[0]) {
18                return a[1] - b[1];  // Same value: sort by index ascending
19            }
20            return b[0] - a[0];      // Different values: sort by value descending
21        });
22      
23        // TreeSet to maintain sorted indices of elements processed so far
24        TreeSet<Integer> processedIndices = new TreeSet<>();
25      
26        // Process elements from largest to smallest
27        for (int[] pair : valueIndexPairs) {
28            int currentIndex = pair[1];
29          
30            // Find the first index greater than current index
31            Integer firstGreaterIndex = processedIndices.higher(currentIndex);
32          
33            // If first greater index exists, find the second greater index
34            if (firstGreaterIndex != null) {
35                Integer secondGreaterIndex = processedIndices.higher(firstGreaterIndex);
36              
37                // If second greater index exists, update result
38                if (secondGreaterIndex != null) {
39                    result[currentIndex] = nums[secondGreaterIndex];
40                }
41            }
42          
43            // Add current index to the set of processed indices
44            processedIndices.add(currentIndex);
45        }
46      
47        return result;
48    }
49}
50

1class Solution {
2public:
3    vector<int> secondGreaterElement(vector<int>& nums) {
4        int n = nums.size();
5        vector<int> result(n, -1);  // Initialize result array with -1 (no second greater element)
6      
7        // Create pairs of (negative value, original index) for sorting
8        // Using negative values to sort in descending order of original values
9        vector<pair<int, int>> valueIndexPairs(n);
10        for (int i = 0; i < n; ++i) {
11            valueIndexPairs[i] = {-nums[i], i};
12        }
13      
14        // Sort pairs: larger original values come first (due to negation)
15        sort(valueIndexPairs.begin(), valueIndexPairs.end());
16      
17        // Set to maintain indices of processed elements in sorted order
18        set<int> processedIndices;
19      
20        // Process elements from largest to smallest value
21        for (const auto& [negativeValue, currentIndex] : valueIndexPairs) {
22            // Find the first index greater than current index
23            auto firstGreaterIt = processedIndices.upper_bound(currentIndex);
24          
25            if (firstGreaterIt != processedIndices.end()) {
26                // Found first greater index, now find second greater index
27                auto secondGreaterIt = processedIndices.upper_bound(*firstGreaterIt);
28              
29                if (secondGreaterIt != processedIndices.end()) {
30                    // Found second greater element, store its value
31                    result[currentIndex] = nums[*secondGreaterIt];
32                }
33            }
34          
35            // Add current index to the set of processed indices
36            processedIndices.insert(currentIndex);
37        }
38      
39        return result;
40    }
41};
42

1// Type definitions
2type CompareFunction<T> = (lhs: T, rhs: T) => number;
3
4// Node structure for Red-Black Tree
5interface RBTreeNode<T = number> {
6    data: T;
7    count: number;
8    left: RBTreeNode<T> | null;
9    right: RBTreeNode<T> | null;
10    parent: RBTreeNode<T> | null;
11    color: number; // 0: red, 1: black
12}
13
14// TreeSet structure
15interface TreeSet<T = number> {
16    size: number;
17    root: RBTreeNode<T> | null;
18    compare: CompareFunction<T>;
19}
20
21/**
22 * Find the second greater element for each element in the array
23 * @param nums - Input array of numbers
24 * @returns Array where each element is the second greater element to its right, or -1 if none exists
25 */
26function secondGreaterElement(nums: number[]): number[] {
27    const n = nums.length;
28  
29    // Create array of [value, index] pairs
30    const valueIndexPairs: [number, number][] = [];
31    for (let i = 0; i < n; ++i) {
32        valueIndexPairs.push([nums[i], i]);
33    }
34  
35    // Sort by value (descending), then by index (ascending) if values are equal
36    valueIndexPairs.sort((a, b) => 
37        a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]
38    );
39  
40    // Initialize result array with -1
41    const result = Array(n).fill(-1);
42  
43    // Create a TreeSet to maintain sorted indices
44    const indexSet = createTreeSet<number>();
45  
46    // Process each element from largest to smallest
47    for (const [_, index] of valueIndexPairs) {
48        // Find the first index greater than current
49        let nextIndex = findHigher(indexSet, index);
50      
51        if (nextIndex !== undefined) {
52            // Find the second index greater than current
53            nextIndex = findHigher(indexSet, nextIndex);
54            if (nextIndex !== undefined) {
55                result[index] = nums[nextIndex];
56            }
57        }
58      
59        // Add current index to the set
60        addToTreeSet(indexSet, index);
61    }
62  
63    return result;
64}
65
66// Red-Black Tree Node helper functions
67
68/**
69 * Create a new Red-Black Tree node
70 */
71function createRBTreeNode<T>(data: T): RBTreeNode<T> {
72    return {
73        data,
74        left: null,
75        right: null,
76        parent: null,
77        color: 0, // New nodes are red by default
78        count: 1
79    };
80}
81
82/**
83 * Get the sibling of a node
84 */
85function getSibling<T>(node: RBTreeNode<T>): RBTreeNode<T> | null {
86    if (!node.parent) return null;
87    return isLeftChild(node) ? node.parent.right : node.parent.left;
88}
89
90/**
91 * Check if node is left child of its parent
92 */
93function isLeftChild<T>(node: RBTreeNode<T>): boolean {
94    return node === node.parent?.left;
95}
96
97/**
98 * Check if node has at least one red child
99 */
100function hasRedChild<T>(node: RBTreeNode<T>): boolean {
101    return (node.left?.color === 0) || (node.right?.color === 0);
102}
103
104// Red-Black Tree rotation and balancing functions
105
106/**
107 * Perform left rotation on the given node
108 */
109function rotateLeft<T>(treeSet: TreeSet<T>, pivotNode: RBTreeNode<T>): void {
110    const rightChild = pivotNode.right!;
111    pivotNode.right = rightChild.left;
112  
113    if (pivotNode.right) {
114        pivotNode.right.parent = pivotNode;
115    }
116  
117    rightChild.parent = pivotNode.parent;
118  
119    if (!pivotNode.parent) {
120        treeSet.root = rightChild;
121    } else if (pivotNode === pivotNode.parent.left) {
122        pivotNode.parent.left = rightChild;
123    } else {
124        pivotNode.parent.right = rightChild;
125    }
126  
127    rightChild.left = pivotNode;
128    pivotNode.parent = rightChild;
129}
130
131/**
132 * Perform right rotation on the given node
133 */
134function rotateRight<T>(treeSet: TreeSet<T>, pivotNode: RBTreeNode<T>): void {
135    const leftChild = pivotNode.left!;
136    pivotNode.left = leftChild.right;
137  
138    if (pivotNode.left) {
139        pivotNode.left.parent = pivotNode;
140    }
141  
142    leftChild.parent = pivotNode.parent;
143  
144    if (!pivotNode.parent) {
145        treeSet.root = leftChild;
146    } else if (pivotNode === pivotNode.parent.left) {
147        pivotNode.parent.left = leftChild;
148    } else {
149        pivotNode.parent.right = leftChild;
150    }
151  
152    leftChild.right = pivotNode;
153    pivotNode.parent = leftChild;
154}
155
156/**
157 * Swap colors of two nodes
158 */
159function swapColors<T>(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
160    const tempColor = node1.color;
161    node1.color = node2.color;
162    node2.color = tempColor;
163}
164
165/**
166 * Fix Red-Black Tree properties after insertion
167 */
168function fixAfterInsert<T>(treeSet: TreeSet<T>, node: RBTreeNode<T>): void {
169    let currentNode = node;
170  
171    // Fix violations while node is not root, not black, and parent is red
172    while (currentNode !== treeSet.root && 
173           currentNode.color !== 1 && 
174           currentNode.parent?.color === 0) {
175      
176        const parent = currentNode.parent;
177        const grandParent = parent.parent;
178      
179        if (parent === grandParent?.left) {
180            // Parent is left child of grandparent
181            const uncle = grandParent.right;
182          
183            if (uncle?.color === 0) {
184                // Case 1: Uncle is red - only recoloring needed
185                grandParent.color = 0;
186                parent.color = 1;
187                uncle.color = 1;
188                currentNode = grandParent;
189            } else {
190                // Uncle is black or null
191                if (currentNode === parent.right) {
192                    // Case 2: Node is right child - left rotation needed
193                    rotateLeft(treeSet, parent);
194                    currentNode = parent;
195                }
196              
197                // Case 3: Node is left child - right rotation needed
198                rotateRight(treeSet, grandParent);
199                swapColors(currentNode.parent!, grandParent);
200                currentNode = currentNode.parent!;
201            }
202        } else {
203            // Parent is right child of grandparent
204            const uncle = grandParent!.left;
205          
206            if (uncle?.color === 0) {
207                // Case 1: Uncle is red - only recoloring needed
208                grandParent!.color = 0;
209                parent.color = 1;
210                uncle.color = 1;
211                currentNode = grandParent!;
212            } else {
213                // Uncle is black or null
214                if (currentNode === parent.left) {
215                    // Case 2: Node is left child - right rotation needed
216                    rotateRight(treeSet, parent);
217                    currentNode = parent;
218                }
219              
220                // Case 3: Node is right child - left rotation needed
221                rotateLeft(treeSet, grandParent!);
222                swapColors(currentNode.parent!, grandParent!);
223                currentNode = currentNode.parent!;
224            }
225        }
226    }
227  
228    // Ensure root is always black
229    treeSet.root!.color = 1;
230}
231
232// TreeSet operations
233
234/**
235 * Create a new TreeSet
236 */
237function createTreeSet<T = number>(
238    compare: CompareFunction<T> = (a: T, b: T) => (a < b ? -1 : a > b ? 1 : 0)
239): TreeSet<T> {
240    return {
241        size: 0,
242        root: null,
243        compare
244    };
245}
246
247/**
248 * Insert a value into the TreeSet
249 */
250function addToTreeSet<T>(treeSet: TreeSet<T>, value: T): boolean {
251    // Find insertion position
252    let parent = treeSet.root;
253    let insertLeft = false;
254  
255    while (parent) {
256        const comparison = treeSet.compare(value, parent.data);
257      
258        if (comparison < 0) {
259            if (!parent.left) {
260                insertLeft = true;
261                break;
262            }
263            parent = parent.left;
264        } else if (comparison > 0) {
265            if (!parent.right) {
266                insertLeft = false;
267                break;
268            }
269            parent = parent.right;
270        } else {
271            // Value already exists, increment count
272            parent.count++;
273            return false;
274        }
275    }
276  
277    // Create and insert new node
278    const newNode = createRBTreeNode(value);
279  
280    if (!parent) {
281        // Tree is empty
282        treeSet.root = newNode;
283    } else if (insertLeft) {
284        parent.left = newNode;
285    } else {
286        parent.right = newNode;
287    }
288  
289    newNode.parent = parent;
290  
291    // Fix Red-Black Tree properties
292    fixAfterInsert(treeSet, newNode);
293    treeSet.size++;
294  
295    return true;
296}
297
298/**
299 * Find the smallest value greater than the given value
300 */
301function findHigher<T>(treeSet: TreeSet<T>, value: T): T | undefined {
302    let currentNode = treeSet.root;
303    let result: RBTreeNode<T> | null = null;
304  
305    // Binary search for the smallest value greater than input
306    while (currentNode) {
307        if (treeSet.compare(value, currentNode.data) < 0) {
308            // Current node's value is greater than input
309            result = currentNode;
310            currentNode = currentNode.left; // Look for smaller values
311        } else {
312            // Current node's value is less than or equal to input
313            currentNode = currentNode.right; // Look for larger values
314        }
315    }
316  
317    return result?.data;
318}
319
320/**
321 * Find the largest value less than the given value
322 */
323function findLower<T>(treeSet: TreeSet<T>, value: T): T | undefined {
324    let currentNode = treeSet.root;
325    let result: RBTreeNode<T> | null = null;
326  
327    // Binary search for the largest value less than input
328    while (currentNode) {
329        if (treeSet.compare(currentNode.data, value) < 0) {
330            // Current node's value is less than input
331            result = currentNode;
332            currentNode = currentNode.right; // Look for larger values
333        } else {
334            // Current node's value is greater than or equal to input
335            currentNode = currentNode.left; // Look for smaller values
336        }
337    }
338  
339    return result?.data;
340}
341

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by three main operations:

Creating the array of tuples arr: O(n)
Sorting arr by value in descending order: O(n × log n)
Iterating through arr and performing operations with SortedList: O(n × log n)
- Each bisect_right() operation takes O(log n) time
- Each add() operation takes O(log n) time to maintain sorted order
- We perform both operations n times

Since these operations are sequential, the overall time complexity is O(n) + O(n × log n) + O(n × log n) = O(n × log n).

Space Complexity: O(n)

The space complexity comes from:

The arr list containing n tuples: O(n)
The SortedList which can contain up to n elements: O(n)
The ans list of size n: O(n)

All these data structures use linear space, resulting in a total space complexity of O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Misunderstanding the Index Relationship in SortedList

The Problem: A common mistake is misinterpreting what bisect_right(current_index) returns and how it relates to finding the "second greater" element. Developers often confuse:

The position in the SortedList (what bisect_right returns)
The actual indices stored in the SortedList
Which element represents the "second greater"

Example of the Mistake:

# INCORRECT interpretation
position = processed_indices.bisect_right(current_index)
# Wrong: Thinking position itself is an index in nums
result[current_index] = nums[position + 1]  # This would cause IndexError or wrong result

Why This Happens: When bisect_right(current_index) returns a value like 2, it means there are 2 indices in the SortedList that are greater than current_index. However, these indices might be something like [5, 7] - not [0, 1]. The confusion arises because:

position is just a count/position in the SortedList
processed_indices[position] gives you the actual array index
You need processed_indices[position + 1] for the second greater element's index

The Correct Solution:

# CORRECT implementation
position = processed_indices.bisect_right(current_index)
if position + 1 < len(processed_indices):
    # Get the actual index from the SortedList at position+1
    second_greater_index = processed_indices[position + 1]
    # Use that index to get the value from nums
    result[current_index] = nums[second_greater_index]

Visual Example: For nums = [2, 4, 0, 9, 6], when processing element 0 at index 2:

processed_indices might be [1, 3, 4] (indices of elements 4, 9, and 6)
bisect_right(2) returns 1 (index 2 would go after position 0 but before position 1)
processed_indices[1] = 3 (first greater element's index)
processed_indices[2] = 4 (second greater element's index)
So result[2] = nums[4] = 6

Key Takeaway: Always remember that SortedList operations return positions within the list, not the actual values stored in the list. You must use these positions to access the actual indices, then use those indices to access values in the original array.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know