Watch 2 video solutions for Maximal Range That Each Element Is Maximum in It, a medium level problem involving Array, Stack, Monotonic Stack. This walkthrough by Programming Live with Larry has 229 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i] <= 105nums are distinct.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Expansion | O(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 |