Maximal Range That Each Element Is Maximum in It
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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 subarraynums[l..r], such that the maximum element in that subarray is equal tonums[i].
Return the arrayans.
Note that a subarray is a contiguous part of the array.
Examples
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 <= 10^51 <= nums[i] <= 10^5- All elements in
numsare distinct.
Solution
Method 1 – Monotonic Stack for Previous and Next Greater
Intuition
For each element, the maximal subarray where it is the maximum is bounded by the first greater element to the left and right. Using a monotonic stack, we can efficiently find these bounds for all elements.
Approach
- For each index, find the previous greater element's index (to the left) using a decreasing stack.
- For each index, find the next greater element's index (to the right) using a decreasing stack.
- The maximal range for
nums[i]is fromprev[i] + 1tonext[i] - 1, so the length isnext[i] - prev[i] - 1. - Store the result in
ansand return it.
Code
C++
class Solution {
public:
vector<int> maximumLength(vector<int>& nums) {
int n = nums.size();
vector<int> prev(n, -1), next(n, n), ans(n);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && nums[st.top()] < nums[i]) st.pop();
if (!st.empty()) prev[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n-1; i >= 0; --i) {
while (!st.empty() && nums[st.top()] < nums[i]) st.pop();
if (!st.empty()) next[i] = st.top();
st.push(i);
}
for (int i = 0; i < n; ++i) {
ans[i] = next[i] - prev[i] - 1;
}
return ans;
}
};
Go
func maximumLength(nums []int) []int {
n := len(nums)
prev := make([]int, n)
next := make([]int, n)
for i := range prev {
prev[i] = -1
next[i] = n
}
st := []int{}
for i := 0; i < n; i++ {
for len(st) > 0 && nums[st[len(st)-1]] < nums[i] {
st = st[:len(st)-1]
}
if len(st) > 0 {
prev[i] = st[len(st)-1]
}
st = append(st, i)
}
st = st[:0]
for i := n-1; i >= 0; i-- {
for len(st) > 0 && nums[st[len(st)-1]] < nums[i] {
st = st[:len(st)-1]
}
if len(st) > 0 {
next[i] = st[len(st)-1]
}
st = append(st, i)
}
ans := make([]int, n)
for i := 0; i < n; i++ {
ans[i] = next[i] - prev[i] - 1
}
return ans
}
Java
class Solution {
public int[] maximumLength(int[] nums) {
int n = nums.length;
int[] prev = new int[n], next = new int[n], ans = new int[n];
Arrays.fill(prev, -1);
Arrays.fill(next, n);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && nums[st.peek()] < nums[i]) st.pop();
if (!st.isEmpty()) prev[i] = st.peek();
st.push(i);
}
st.clear();
for (int i = n-1; i >= 0; i--) {
while (!st.isEmpty() && nums[st.peek()] < nums[i]) st.pop();
if (!st.isEmpty()) next[i] = st.peek();
st.push(i);
}
for (int i = 0; i < n; i++) {
ans[i] = next[i] - prev[i] - 1;
}
return ans;
}
}
Kotlin
class Solution {
fun maximumLength(nums: IntArray): IntArray {
val n = nums.size
val prev = IntArray(n) { -1 }
val next = IntArray(n) { n }
val ans = IntArray(n)
val st = ArrayDeque<Int>()
for (i in 0 until n) {
while (st.isNotEmpty() && nums[st.last()] < nums[i]) st.removeLast()
if (st.isNotEmpty()) prev[i] = st.last()
st.addLast(i)
}
st.clear()
for (i in n-1 downTo 0) {
while (st.isNotEmpty() && nums[st.last()] < nums[i]) st.removeLast()
if (st.isNotEmpty()) next[i] = st.last()
st.addLast(i)
}
for (i in 0 until n) {
ans[i] = next[i] - prev[i] - 1
}
return ans
}
}
Python
class Solution:
def maximumLength(self, nums: list[int]) -> list[int]:
n = len(nums)
prev = [-1] * n
next_ = [n] * n
st = []
for i in range(n):
while st and nums[st[-1]] < nums[i]:
st.pop()
if st:
prev[i] = st[-1]
st.append(i)
st.clear()
for i in range(n-1, -1, -1):
while st and nums[st[-1]] < nums[i]:
st.pop()
if st:
next_[i] = st[-1]
st.append(i)
return [next_[i] - prev[i] - 1 for i in range(n)]
Rust
impl Solution {
pub fn maximum_length(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut prev = vec![-1; n];
let mut next = vec![n as i32; n];
let mut st = Vec::new();
for i in 0..n {
while let Some(&top) = st.last() {
if nums[top] < nums[i] {
st.pop();
} else {
break;
}
}
if let Some(&top) = st.last() {
prev[i] = top as i32;
}
st.push(i);
}
st.clear();
for i in (0..n).rev() {
while let Some(&top) = st.last() {
if nums[top] < nums[i] {
st.pop();
} else {
break;
}
}
if let Some(&top) = st.last() {
next[i] = top as i32;
}
st.push(i);
}
(0..n).map(|i| next[i] - prev[i] - 1).collect()
}
}
TypeScript
class Solution {
maximumLength(nums: number[]): number[] {
const n = nums.length;
const prev = Array(n).fill(-1), next = Array(n).fill(n);
const ans = Array(n);
const st: number[] = [];
for (let i = 0; i < n; i++) {
while (st.length && nums[st[st.length-1]] < nums[i]) st.pop();
if (st.length) prev[i] = st[st.length-1];
st.push(i);
}
st.length = 0;
for (let i = n-1; i >= 0; i--) {
while (st.length && nums[st[st.length-1]] < nums[i]) st.pop();
if (st.length) next[i] = st[st.length-1];
st.push(i);
}
for (let i = 0; i < n; i++) {
ans[i] = next[i] - prev[i] - 1;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n), wherenis the length of the array, since each element is pushed and popped from the stack at most once. - 🧺 Space complexity:
O(n), for storing the stack and result arrays.