Skip to main content
Talentd

Maximal Range That Each Element Is Maximum in It - Solution & Explanation

MediumPremiumFree on FleetCodeArrayStackMonotonic Stack7 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given a 0-indexed array nums of distinct integers.

Let us define a 0-indexed array ans of the same length as nums in the following way:

  • ans[i] is the maximum length of a subarray nums[l..r], such that the maximum element in that subarray is equal to nums[i].

Return the array ans.

Note that a subarray is a contiguous part of the array.

 

Example 1:

Input: nums = [1,5,4,3,6]
Output: [1,4,2,1,5]
Explanation: For nums[0] the longest subarray in which 1 is the maximum is nums[0..0] so ans[0] = 1.
For nums[1] the longest subarray in which 5 is the maximum is nums[0..3] so ans[1] = 4.
For nums[2] the longest subarray in which 4 is the maximum is nums[2..3] so ans[2] = 2.
For nums[3] the longest subarray in which 3 is the maximum is nums[3..3] so ans[3] = 1.
For nums[4] the longest subarray in which 6 is the maximum is nums[0..4] so ans[4] = 5.

Example 2:

Input: nums = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: For nums[i] the longest subarray in which it's the maximum is nums[0..i] so ans[i] = i + 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • All elements in nums are distinct.

Approach Overview

Problem Overview: You receive an integer array and must determine the maximum continuous range where each element remains the largest value in that range. For every index, compute how far it can extend left and right while still being the maximum element.

Approach 1: Brute Force Expansion (O(n²) time, O(1) space)

For each index, expand outward to the left and right until you encounter a number greater than the current element. The valid segment is bounded by those greater elements. This directly models the definition of the problem but requires scanning potentially the entire array for every element. The implementation is straightforward with nested loops, but the worst‑case complexity becomes quadratic, which is inefficient for large inputs.

Approach 2: Monotonic Stack (O(n) time, O(n) space)

The optimal solution relies on a monotonic stack to efficiently find the nearest greater element on both sides of every index. Traverse the array while maintaining a decreasing stack of indices. When a larger element appears, pop smaller elements and record their next greater boundary. A second pass (or reverse traversal) finds the previous greater boundary. Once you know the closest greater element to the left and right, the maximal range for index i becomes (leftGreater + 1) to (rightGreater - 1). This avoids repeated scanning because each index is pushed and popped at most once.

This pattern is common in stack-based array problems such as Largest Rectangle in Histogram or Sum of Subarray Minimums. The stack enforces an order that lets you determine dominance boundaries efficiently. Conceptually, every element "controls" a region until a larger element breaks it.

The algorithm processes the array in linear time. For each element, the stack maintains candidates whose ranges are still expanding. When a greater element appears, the previous candidate’s maximum span ends.

Recommended for interviews: Interviewers expect the monotonic stack approach. Starting with the brute force explanation shows you understand the range definition, but switching to the stack solution demonstrates knowledge of a common optimization pattern used in many array dominance problems. The O(n) solution is both optimal and scalable.

Solution

This problem is a template for monotonic stack. We only need to use the monotonic stack to find the position of the first element larger than nums[i] on the left and right, denoted as left[i] and right[i]. Then, the interval length with nums[i] as the maximum value is right[i] - left[i] - 1.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ExpansionO(n²)O(1)Small arrays or when explaining the core idea before optimization
Monotonic Stack (Previous + Next Greater)O(n)O(n)General case and interview‑optimal solution for large arrays

Video Solution

2832. Maximal Range That Each Element Is Maximum in It - Week 3/5 Leetcode December Challenge • Programming Live with Larry • 230 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximal Range That Each Element Is Maximum in It easy or hard?
The problem is usually classified as Medium difficulty. The challenge is recognizing that each element’s valid range is defined by the nearest greater elements, which naturally leads to a monotonic stack solution.
Maximal Range That Each Element Is Maximum in It Python/Java solution
The typical implementation maintains a stack of indices while iterating through the array. When a larger element appears, smaller elements are popped and their right boundary is recorded. The same logic works in Python, Java, C++, Go, and TypeScript with identical O(n) complexity.
How to solve Maximal Range That Each Element Is Maximum in It in O(n)?
Compute the nearest greater element on both sides using a monotonic decreasing stack. During traversal, pop elements when a larger value appears and record the right boundary. A reverse pass or separate stack computation finds the left boundary. The maximum valid range for each index is between these two boundaries.
What is the best approach for Maximal Range That Each Element Is Maximum in It?
The most efficient approach uses a monotonic decreasing stack to find the nearest greater element on both the left and right of every index. These boundaries determine how far each element can extend while remaining the maximum. The algorithm runs in O(n) time and O(n) space because each element is pushed and popped from the stack at most once.
Is Maximal Range That Each Element Is Maximum in It asked at Google/Amazon/Meta?
Problems based on monotonic stacks and nearest greater elements frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as Largest Rectangle in Histogram and Sum of Subarray Minimums test the same core technique used in this problem.
What data structure is used in Maximal Range That Each Element Is Maximum in It?
The key data structure is a monotonic stack that stores array indices in decreasing order of values. This structure helps efficiently determine previous and next greater elements without scanning the array repeatedly.
What is the time complexity of Maximal Range That Each Element Is Maximum in It?
The optimal monotonic stack solution runs in O(n) time with O(n) extra space. Each element is processed once when pushed to the stack and once when popped. A brute force method that expands left and right for every element takes O(n²) time.

Ready to solve this problem?

Practice Maximal Range That Each Element Is Maximum in It with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays