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 subarray nums[l..r], such that the maximum element in that subarray is equal to nums[i].

Return the arrayans.

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

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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^5
  • 1 <= nums[i] <= 10^5
  • All elements in nums are 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

  1. For each index, find the previous greater element’s index (to the left) using a decreasing stack.
  2. For each index, find the next greater element’s index (to the right) using a decreasing stack.
  3. The maximal range for nums[i] is from prev[i] + 1 to next[i] - 1, so the length is next[i] - prev[i] - 1.
  4. Store the result in ans and return it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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)]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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), where n is 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.