Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

LeetCode 2832 - Maximal Range That Each Element Is Maximum in It

Problem Understanding

We are given an array nums consisting of distinct integers. For every position i, we need to determine the maximum possible length of a contiguous subarray in which nums[i] is the largest element.

More formally, for each index i, we want to find the longest subarray nums[l..r] satisfying:

l <= i <= r
The maximum value inside nums[l..r] is exactly nums[i]

The output array ans should have the same length as nums, where ans[i] stores this maximum possible subarray length for index i.

Since all elements are distinct, every subarray has exactly one maximum element. This guarantee is extremely important because it eliminates ambiguity when determining which element is the maximum.

Consider the meaning of the answer for a particular element. If nums[i] = 5, then we want the largest interval containing index i such that no element greater than 5 appears anywhere in that interval. The moment we include an element larger than 5, then 5 is no longer the maximum.

The constraints are:

1 <= nums.length <= 100000
1 <= nums[i] <= 100000
All elements are distinct

The array length can be as large as 100000, which immediately rules out quadratic solutions. Any approach that examines all subarrays or expands independently from every position will be too slow.

Important edge cases include:

A single-element array.
A strictly increasing array.
A strictly decreasing array.
The global maximum element, whose valid range may span the entire array.
Elements near larger neighbors, whose range may collapse to length 1.

Approaches

Brute Force

A straightforward solution is to process each index independently.

For every position i, expand left and right while all encountered elements remain smaller than nums[i]. The expansion must stop when we encounter a larger element because that larger value would become the maximum of the subarray.

After finding the furthest valid left and right boundaries, the answer is:

right - left + 1

This works because every valid subarray containing i must stay between the nearest greater element on the left and the nearest greater element on the right.

The problem is that finding those boundaries by scanning outward for every index can take O(n) time per element. With n elements, the total complexity becomes O(n²).

For n = 100000, this is far too slow.

Key Insight

For an element to remain the maximum of a subarray, the subarray cannot contain any element larger than it.

Therefore, for each index i, we only need:

The nearest greater element on the left.
The nearest greater element on the right.

These two greater elements form barriers that cannot be crossed.

If:

leftGreater[i] is the index of the nearest greater element on the left, or -1 if none exists.
rightGreater[i] is the index of the nearest greater element on the right, or n if none exists.

Then the largest valid interval is:

(leftGreater[i] + 1) ... (rightGreater[i] - 1)

Its length is:

rightGreater[i] - leftGreater[i] - 1

The remaining challenge is finding nearest greater elements efficiently.

A monotonic decreasing stack solves this in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Expand from every index independently
Optimal	O(n)	O(n)	Monotonic stack finds nearest greater elements

Algorithm Walkthrough

Step 1: Find nearest greater element on the left

Create an array leftGreater initialized with -1.

Traverse from left to right while maintaining a monotonic decreasing stack of indices.

For each index i:

Pop indices while their values are smaller than nums[i].
After popping, the stack top is the nearest greater element on the left.
Store that index in leftGreater[i].
Push i onto the stack.

The stack remains decreasing in value.

Step 2: Find nearest greater element on the right

Create an array rightGreater initialized with n.

Clear the stack.

Traverse from right to left.

For each index i:

Pop indices while their values are smaller than nums[i].
After popping, the stack top is the nearest greater element on the right.
Store that index in rightGreater[i].
Push i onto the stack.

Again, the stack remains decreasing in value.

Step 3: Compute the maximal range

For every index i:

The nearest greater element on the left blocks expansion beyond it.
The nearest greater element on the right blocks expansion beyond it.
Therefore the maximal valid interval is between those barriers.

Compute:

ans[i] = rightGreater[i] - leftGreater[i] - 1

Step 4: Return the result

Return the constructed answer array.

Why it works

For any index i, every element between the nearest greater element on the left and the nearest greater element on the right is strictly smaller than nums[i]. Therefore nums[i] remains the maximum throughout that entire interval.

Crossing either boundary would include a larger element, which would immediately become the maximum and invalidate the interval.

Since these are the closest greater elements, the interval between them is the largest possible valid interval. Thus the computed length is exactly the maximum subarray length in which nums[i] is the maximum.

Python Solution

from typing import List

class Solution:
    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
        n = len(nums)

        left_greater = [-1] * n
        stack = []

        for i in range(n):
            while stack and nums[stack[-1]] < nums[i]:
                stack.pop()

            if stack:
                left_greater[i] = stack[-1]

            stack.append(i)

        right_greater = [n] * n
        stack.clear()

        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] < nums[i]:
                stack.pop()

            if stack:
                right_greater[i] = stack[-1]

            stack.append(i)

        ans = [0] * n

        for i in range(n):
            ans[i] = right_greater[i] - left_greater[i] - 1

        return ans

The implementation follows the algorithm directly.

The first pass computes the nearest greater element on the left. The stack stores indices whose corresponding values form a decreasing sequence. Whenever a larger value appears, smaller values can never serve as a nearest greater element for future positions, so they are removed.

The second pass performs the same idea from right to left to compute nearest greater elements on the right.

After both boundary arrays are available, each answer is simply the width of the interval between the two blocking greater elements. This final computation requires one linear pass.

Go Solution

func maximumLengthOfRanges(nums []int) []int {
	n := len(nums)

	leftGreater := make([]int, n)
	for i := range leftGreater {
		leftGreater[i] = -1
	}

	stack := []int{}

	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			leftGreater[i] = stack[len(stack)-1]
		}

		stack = append(stack, i)
	}

	rightGreater := make([]int, n)
	for i := range rightGreater {
		rightGreater[i] = n
	}

	stack = stack[:0]

	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			rightGreater[i] = stack[len(stack)-1]
		}

		stack = append(stack, i)
	}

	ans := make([]int, n)

	for i := 0; i < n; i++ {
		ans[i] = rightGreater[i] - leftGreater[i] - 1
	}

	return ans
}

The Go implementation mirrors the Python solution closely. Slices are used to implement the stack. Reusing the same slice with stack = stack[:0] avoids allocating a second stack. Since all arithmetic involves indices bounded by 100000, integer overflow is not a concern.

Worked Examples

Example 1

Input:

nums = [1, 5, 4, 3, 6]

Left greater pass

i	nums[i]	Stack After Processing	leftGreater
0	1	[0]	-1
1	5	[1]	-1
2	4	[1,2]	1
3	3	[1,2,3]	2
4	6	[4]	-1

Result:

leftGreater = [-1, -1, 1, 2, -1]

Right greater pass

i	nums[i]	Stack After Processing	rightGreater
4	6	[4]	5
3	3	[4,3]	4
2	4	[4,2]	4
1	5	[4,1]	4
0	1	[4,1,0]	1

Result:

rightGreater = [1, 4, 4, 4, 5]

Final answers

Index	Formula	Answer
0	1 - (-1) - 1	1
1	4 - (-1) - 1	4
2	4 - 1 - 1	2
3	4 - 2 - 1	1
4	5 - (-1) - 1	5

Output:

[1, 4, 2, 1, 5]

Example 2

Input:

nums = [1,2,3,4,5]

Left greater

[-1, -1, -1, -1, -1]

Every new element is larger than everything before it.

Right greater

[1, 2, 3, 4, 5]

Each element's nearest greater element is immediately to its right.

Final answers

Index	Length
0	1
1	2
2	3
3	4
4	5

Output:

[1,2,3,4,5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is pushed and popped at most once in each stack pass
Space	O(n)	Boundary arrays and stack storage

The crucial observation is that the monotonic stack performs amortized constant work per element. Although the inner while loops appear expensive, each index can only be removed from the stack once. Therefore the total number of stack operations across the entire algorithm is linear, giving an overall time complexity of O(n).

Test Cases

from typing import List

s = Solution()

assert s.maximumLengthOfRanges([1, 5, 4, 3, 6]) == [1, 4, 2, 1, 5]  # example 1
assert s.maximumLengthOfRanges([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]  # example 2

assert s.maximumLengthOfRanges([7]) == [1]  # single element

assert s.maximumLengthOfRanges([5, 4, 3, 2, 1]) == [5, 4, 3, 2, 1]  # decreasing array

assert s.maximumLengthOfRanges([2, 1]) == [2, 1]  # two elements decreasing

assert s.maximumLengthOfRanges([1, 2]) == [1, 2]  # two elements increasing

assert s.maximumLengthOfRanges([3, 1, 2]) == [3, 1, 2]  # local maximum at front

assert s.maximumLengthOfRanges([2, 5, 1, 4, 3]) == [1, 5, 1, 3, 1]  # mixed pattern

assert s.maximumLengthOfRanges([4, 1, 3, 2]) == [4, 1, 3, 1]  # internal barriers

assert s.maximumLengthOfRanges([1, 3, 2, 5, 4]) == [1, 3, 1, 5, 1]  # multiple peaks

Test Summary

Test	Why
`[1,5,4,3,6]`	Official example with mixed ordering
`[1,2,3,4,5]`	Strictly increasing sequence
`[7]`	Minimum array size
`[5,4,3,2,1]`	Strictly decreasing sequence
`[2,1]`	Small decreasing case
`[1,2]`	Small increasing case
`[3,1,2]`	Maximum element at beginning
`[2,5,1,4,3]`	Mixed arrangement with multiple barriers
`[4,1,3,2]`	Internal greater elements limit expansion
`[1,3,2,5,4]`	Multiple local maxima and minima

Edge Cases

Single Element Array

When nums contains only one element, there are no neighbors and therefore no greater elements on either side. The only valid subarray is the element itself, so the answer is [1].

The implementation handles this naturally because the left boundary remains -1, the right boundary remains n, and the formula produces a length of 1.

Strictly Increasing Array

For an increasing array such as [1,2,3,4,5], every element except the last has a greater element immediately to its right.

This means each element can only expand leftward. The nearest greater element on the right becomes the limiting barrier. The monotonic stack correctly identifies these boundaries and produces [1,2,3,4,5].

Strictly Decreasing Array

For a decreasing array such as [5,4,3,2,1], every element except the first has a greater element immediately to its left.

In this situation, expansion is only possible to the right. The nearest greater element on the left acts as the barrier. The algorithm still works because left and right boundaries are computed independently and symmetrically.

Global Maximum Element

The largest element in the entire array has no greater element on either side.

Therefore its nearest greater boundaries become -1 and n, allowing it to span the entire array. The formula correctly yields a range length of n.

Elements Trapped Between Larger Neighbors

An element may have a larger value immediately on both sides. For example, the middle element 1 in [5,1,4].

In this case both boundaries are adjacent to the element, producing a range length of 1. The algorithm handles this automatically through the nearest greater element computation.