Next Largest Number to the Right

Find, for each element in an array, the closest element to its right that is strictly greater. This problem tests understanding of data structures for efficient lookups and monotonic stacks.

stackarraymonotonic stacknearest greater element

Problem Statement

Given an array of integers, determine, for each element in the array, the index of the nearest element to its right that is strictly larger than it. If no such element exists, record -1. Return an array containing these indices.

Example 1

Input: [5, 3, 8, 6, 1, 4]

Output: [2, 2, -1, -1, 5, -1]

For 5, the next larger element is 8 at index 2. For 3, the next larger element is 8 at index 2. For 8 and 6, there are no larger elements to the right, so -1. For 1, the next larger element is 4 at index 5, and for 4 there are no larger elements to the right, so -1.

Example 2

Input: [9, 7, 6, 5, 4, 3]

Output: [-1, -1, -1, -1, -1, -1]

Since the array is in strictly decreasing order, no element has a larger element to its right. Therefore, the output is an array of -1s.

Constraints

-1 <= array length <= 10^5
--10^9 <= element value <= 10^9
-Elements in the array are integers.

Brute Force Approach

The brute-force approach is like checking every single house on your street to find the one with a higher number than yours. For each element, iterate through the rest of the array to its right and keep track of the first element that's larger. This involves nested loops, leading to a quadratic time complexity.

TimeO(n^2)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem