# 2832. Maximal Range That Each Element Is Maximum in It

## Problem Description

You are given an array `nums` which contains distinct integers and is 0-indexed. The task is to create another 0-indexed array `ans` which corresponds to the array `nums`. The value at each index `i` in `ans` should be the maximum length of a subarray, denoted as `nums[l..r]`, where `nums[i]` is the largest element in that subarray. The subarray we refer to is a contiguous sequence of elements in the original array, `nums`.

To illustrate, if `nums` is `[1, 3, 2]`, then `ans[1]` (corresponding to `nums[1]`, which is `3`) would be `3`, since the subarray `[1, 3, 2]` with `3` as the maximum element includes all elements in the array.

## Intuition

To solve this problem efficiently, we need to determine, for each element `nums[i]`, the subarray where it is the maximum element. Specifically, we want to find the indices of the first smaller element to the left and the first smaller element to the right of `nums[i]`. These indices essentially bound the subarray where `nums[i]` is the maximum element.

The problem can be tackled using a monotonic stackโa stack that maintains its elements in either non-increasing or non-decreasing order. We'll use a non-increasing stack for our purpose.

The intuition behind using a monotonic stack comes from the need to quickly find elements that are smaller than the current element when we traverse the array. By maintaining a non-increasing stack, we ensure that the moment a number smaller than the top of the stack is encountered, it signifies a boundary.

For each position `i` in the array, we want to find:

1. `left[i]`: the closest index on the left of `i` where `nums[i]` is less than `nums[left[i]]`.
2. `right[i]`: The closest index on the right of `i` where `nums[i]` is less than `nums[right[i]]`.

To find the `left` array values, we iterate through `nums` from left to right, and to find the `right` array values, we iterate from right to left. During each iteration, we:

1. Use the stack to find the next element smaller on the respective side (left or right).
2. When pushing an element onto the stack, pop all elements that are not greater than the current element to maintain the non-increasing order.

Finally, for each index `i`, we can calculate the maximum range as `right[i] - left[i] - 1`, which gives us the length of the largest subarray where `nums[i]` is the maximum element.

The resulting array is the `ans` array that holds the maximum length of ranges for each `nums[i]`.

## Solution Approach

The solution uses a stack as a data structure and a simple algorithm to solve the problem using two passes through the input array. Below is a detailed implementation of the solution approach:

1. Initialize two arrays, `left` and `right`, both of the same length as `nums`. The `left` array will store the indices of the closest smaller number to the left of every number in `nums`, and similarly, the `right` array will store the indices of the closest smaller number to the right of every number in `nums`.

• For `left`, initialize all values to `-1` to represent that there is no smaller number to the left.
• For `right`, initialize all values to `n` (the length of `nums`) to represent that there is no smaller number on the right.
2. Initialize an empty list, `stk`, which will serve as the stack. This stack will help to maintain the indices of numbers in a non-increasing order.

3. Loop through each element `x` in `nums` along with its index `i` using the enumerate function. This loop will fill the `left` array.

• While the stack is not empty and the last element in the stack (`nums[stk[-1]]`) is less than or equal to the current element `x`:
• Pop the element from the stack as it will not be the boundary for any future elements.
• If the stack is not empty after the above step, the current element's left boundary is the last element in the stack, so update `left[i]` with `stk[-1]`.
• Push the current index `i` onto the stack.
4. Reset the stack to an empty list for the next phase of the algorithm.

5. Loop through the elements of `nums` in reverse order, starting from the last index, filling in the `right` array.

• Similar to the forward pass, while the stack isn't empty and the last element in the stack (`nums[stk[-1]]`) is less than or equal to `nums[i]`:
• Pop the element from the stack.
• If the stack is not empty, update the `right[i]` with the last element in the stack, indicating the closest smaller element on the right.
• Push the index `i` onto the stack.
6. After both loops are complete, the `left` and `right` arrays contain the boundaries of the subarray where each element is the maximum.

7. Calculate the maximum length of ranges for each element `nums[i]` by iterating over the `left` and `right` arrays together. For each `i`, subtract the left boundary from the right boundary and subtract `1` to find the length of the subrange. This calculation is done list comprehension style to create the `ans` array:

• `ans = [r - l - 1 for l, r in zip(left, right)]`

The `ans` array now contains the maximum length of the subarray where the ith element is the maximum for all indices `i`.

The main algorithm and data structure patterns used here are:

• Monotonic stack for keeping track of the indices of elements in a non-increasing sequence.
• Two passes through the array to find the ranges: a forward pass for the left boundaries, and a reverse pass for the right boundaries.
• The space complexity of the solution is O(n) due to the additional arrays, and the time complexity is also O(n), because each element is pushed and popped from the stack at most once during each pass.
๐ช
Level Up Your
Algo Skills

### Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the array `nums = [4, 2, 1, 5, 3]`. We want to calculate the array `ans` such that each `ans[i]` contains the maximum length of a subarray where `nums[i]` is the largest element.

1. Initialization:

• Initialize `left` to `[-1, -1, -1, -1, -1]` indicating no smaller elements on the left yet.
• Initialize `right` to `[5, 5, 5, 5, 5]` (since `n = 5` for `nums`) indicating no smaller elements on the right yet.
• Initialize an empty stack `stk`.
2. Forward Pass (for `left` array):

• `i = 0, x = 4`: Stack is empty, push `0`.
• `i = 1, x = 2`: `nums[stk[-1]] = 4` > `2`, so leave the stack unchanged and push `1`.
• `i = 2, x = 1`: `nums[stk[-1]] = 2` > `1`, so leave the stack unchanged and push `2`.
• `i = 3, x = 5`: `nums[stk[-1]] = 1` < `5`, pop `2`. `nums[stk[-1]] = 2` < `5`, pop `1`. `nums[stk[-1]] = 4` < `5`, pop `0`. Stack is now empty, push `3`.
• `i = 4, x = 3`: Stack is not empty, `left[4] = stk[-1] = 3`. Pop `3` since `5` > `3`. Push `4`.

The `left` array is now `[-1, -1, -1, -1, 3]`.

3. Reverse Pass (for `right` array): Reset the stack to `stk = []`.

• `i = 4, x = 3`: Stack is empty, push `4`.
• `i = 3, x = 5`: Stack is not empty, `right[3] = stk[-1] = 4`. Stack keeps `5`.
• `i = 2, x = 1`: `nums[stk[-1]] = 3` > `1`, so leave the stack unchanged, and push `2`.
• `i = 1, x = 2`: `nums[stk[-1]] = 1` < `2`, pop `2`. Now `nums[stk[-1]] = 3` > `2`, so leave the stack and push `1`.
• `i = 0, x = 4`: `nums[stk[-1]] = 2` < `4`, pop `1`. `nums[stk[-1]] = 1` < `4`, pop `2`. Now `nums[stk[-1]] = 3` > `4`, so `right[0] = stk[-1] = 4`, push `0`.

The `right` array is now `[4, 5, 5, 4, 5]`.

• Calculate the length of the largest subarray where each `nums[i]` is the maximum by subtracting `left` indices from `right` indices and reducing by 1.

• The `ans` array is calculated as follows:

``1ans = [right[i] - left[i] - 1 for i in range(len(nums))]``

Thus, `ans = [4 - (-1) - 1, 5 - (-1) - 1, 5 - (-1) - 1, 4 - (-1) - 1, 5 - 3 - 1] = [4, 5, 5, 4, 1]`.

The array `ans = [4, 5, 5, 4, 1]` is the answer to our problem, where each `ans[i]` reflects the maximum subarray length with `nums[i]` as the largest element.

## Python Solution

``````1from typing import List
2
3class Solution:
4    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
5        num_elements = len(nums)
6        # left stores the index of the previous element that is less than nums[i]
7        # If there's no such element, it stores -1
8        left_boundaries = [-1] * num_elements
9        # right stores the index of the next element that is less than nums[i]
10        # If there's no such element, it stores n (length of nums)
11        right_boundaries = [num_elements] * num_elements
12
13        # Stack to keep track of indices where nums[i] is less than the current value
14        stack = []
15
16        # Iterate over each element from the left to find the left boundaries
17        for i, value in enumerate(nums):
18            # Pop from the stack all elements greater than or equal to current value
19            while stack and nums[stack[-1]] <= value:
20                stack.pop()
21            # If stack is not empty, the current value's left boundary is the last element's index
22            if stack:
23                left_boundaries[i] = stack[-1]
24            # Push current index onto the stack
25            stack.append(i)
26
27        # Clear stack for the next iteration
28        stack = []
29
30        # Iterate over each element from the right to find the right boundaries
31        for i in reversed(range(num_elements)):
32            # Pop from the stack all elements greater than or equal to nums[i]
33            while stack and nums[stack[-1]] <= nums[i]:
34                stack.pop()
35            # If stack is not empty, the current value's right boundary is the last element's index
36            if stack:
37                right_boundaries[i] = stack[-1]
38            # Push current index onto the stack
39            stack.append(i)
40
41        # Generate the maximum length of continuous ranges
42        # It's calculated as the difference between right and left boundaries indices minus one
43        return [right - left - 1 for left, right in zip(left_boundaries, right_boundaries)]
44
45# Example usage:
46# solution = Solution()
47# result = solution.maximumLengthOfRanges([10, 5, 2, 6, 5, 3])
48# print(result) # This would print the list of maximum lengths of continuous ranges
49``````

## Java Solution

``````1import java.util.ArrayDeque;
2import java.util.Arrays;
3import java.util.Deque;
4
5class Solution {
6    public int[] maximumLengthOfRanges(int[] nums) {
7        // The number of elements in the input array
8        int n = nums.length;
9
10        // 'left' array to store the index of the previous smaller element
11        int[] left = new int[n];
12        // 'right' array to store the index of the next smaller element
13        int[] right = new int[n];
14
15        // Initialize 'left' array to -1 and 'right' array to 'n'
16        Arrays.fill(left, -1);
17        Arrays.fill(right, n);
18
19        // Stack to keep track of indices while traversing
20        Deque<Integer> stack = new ArrayDeque<>();
21
22        // Traverse the input array from left to right
23        for (int i = 0; i < n; ++i) {
24            // Pop elements from the stack if they are smaller than or equal to current element
25            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
26                stack.pop();
27            }
28            // If stack is not empty, set 'left' at the current index to the top element of the stack
29            if (!stack.isEmpty()) {
30                left[i] = stack.peek();
31            }
32            // Push current index to the stack
33            stack.push(i);
34        }
35
36        // Clear the stack for next traversal
37        stack.clear();
38
39        // Traverse the input array from right to left
40        for (int i = n - 1; i >= 0; --i) {
41            // Pop elements from the stack if they are smaller than or equal to current element
42            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
43                stack.pop();
44            }
45            // If stack is not empty, set 'right' at the current index to the top element of the stack
46            if (!stack.isEmpty()) {
47                right[i] = stack.peek();
48            }
49            // Push current index to the stack
50            stack.push(i);
51        }
52
53        // 'answer' array to store the maximum length ranges
54        int[] answer = new int[n];
55        // Calculate the range length for each element
56        for (int i = 0; i < n; ++i) {
57            // Maximum range length is the difference between right and left indices minus one
58            answer[i] = right[i] - left[i] - 1;
59        }
60
61        // Return the final result array
63    }
64}
65``````

## C++ Solution

``````1#include <vector>
2#include <stack>
3
4class Solution {
5public:
6    // Function to find the maximum length of ranges for each element in nums,
7    // where the range is defined by the next greater element on both sides.
8    std::vector<int> maximumLengthOfRanges(std::vector<int>& nums) {
9        // Get the size of the input vector.
10        int size = nums.size();
11        // Initialize vectors to store the indices of the next greater element on the left and right.
12        std::vector<int> leftIndices(size, -1);
13        std::vector<int> rightIndices(size, size);
14        // Stack to keep track of indices while finding next greater elements.
15        std::stack<int> indexStack;
16
17        // Iterate from the start to find the next greater element on the left.
18        for (int i = 0; i < size; ++i) {
19            // Pop elements from the stack until a greater element is found.
20            while (!indexStack.empty() && nums[indexStack.top()] <= nums[i]) {
21                indexStack.pop();
22            }
23            // If the stack is not empty, the top element is the next greater element on the left.
24            if (!indexStack.empty()) {
25                leftIndices[i] = indexStack.top();
26            }
27            // Push the current index onto the stack.
28            indexStack.push(i);
29        }
30
31        // Clear the stack to reuse it for the right side search.
32        indexStack = std::stack<int>();
33
34        // Iterate from the end to find the next greater element on the right.
35        for (int i = size - 1; i >= 0; --i) {
36            // Pop elements from the stack until a greater element is found.
37            while (!indexStack.empty() && nums[indexStack.top()] <= nums[i]) {
38                indexStack.pop();
39            }
40            // If the stack is not empty, the top element is the next greater element on the right.
41            if (!indexStack.empty()) {
42                rightIndices[i] = indexStack.top();
43            }
44            // Push the current index onto the stack.
45            indexStack.push(i);
46        }
47
48        // Initialize a vector to hold the maximum lengths of ranges.
49        std::vector<int> maxRangeLengths(size);
50
51        // Calculate the maximum range length for each element in nums.
52        for (int i = 0; i < size; ++i) {
53            // The range length is the difference between the right and left indices, minus one.
54            maxRangeLengths[i] = rightIndices[i] - leftIndices[i] - 1;
55        }
56
57        // Return the vector containing maximum range lengths.
58        return maxRangeLengths;
59    }
60};
61``````

## Typescript Solution

``````1function maximumLengthOfRanges(nums: number[]): number[] {
2    const numsLength = nums.length;
3    // 'leftBounds' will hold the index of the previous smaller element for each element.
4    const leftBounds: number[] = Array(numsLength).fill(-1);
5    // 'rightBounds' will hold the index of the next smaller element for each element.
6    const rightBounds: number[] = Array(numsLength).fill(numsLength);
7    const stack: number[] = [];
8
9    // Calculate the previous smaller element's index for each element.
10    for (let i = 0; i < numsLength; ++i) {
11        // Pop elements from the stack until the current element is greater.
12        while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
13            stack.pop();
14        }
15        // If there is a previous smaller element, set its index in 'leftBounds'.
16        if (stack.length) {
17            leftBounds[i] = stack[stack.length - 1];
18        }
19        // Push the current index onto the stack.
20        stack.push(i);
21    }
22
23    // Clear the stack to reuse it for right bounds calculation.
24    stack.length = 0;
25
26    // Calculate the next smaller element's index for each element (reverse iteration).
27    for (let i = numsLength - 1; i >= 0; --i) {
28        // Pop elements from the stack until the current element is greater.
29        while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
30            stack.pop();
31        }
32        // If there is a next smaller element, set its index in 'rightBounds'.
33        if (stack.length) {
34            rightBounds[i] = stack[stack.length - 1];
35        }
36        // Push the current index onto the stack.
37        stack.push(i);
38    }
39
40    // Compute the maximum length of ranges for each element.
41    const maxLengths = leftBounds.map((leftBound, i) => rightBounds[i] - leftBound - 1);
42    return maxLengths;
43}
44``````

## Time and Space Complexity

The given Python code aims to find the maximum length of ranges for each element in a list, where the range is limited by elements that are strictly greater than the current element on both sides.

The time complexity of the code can be analyzed based on the two for-loops used to find the `left` and `right` boundaries for each element:

1. The first for-loop goes through each element in the list `nums` from left to right. For each element at index `i`, it pops elements off the stack `stk` until it finds an element that is greater than `nums[i]`. This operation is essentially an amortized O(1) operation because each element is pushed onto the stack and popped at most once, leading to a total of O(n) operations where `n` is the number of elements in `nums`.

2. The second for-loop is similar to the first one but iterates from right to left. It has the same amortized O(1) complexity per element for the same reason as the first loop.

Taking both loops into account, the overall time complexity of the code is `O(n)`.

For space complexity:

1. The additional space used by the algorithm includes the `stk` stack, the `left`, and `right` arrays. The length of the stack will at most equal the number of elements in `nums` (in the case when the elements are sorted in non-decreasing order), which contributes `O(n)` space complexity.

2. The `left` and `right` arrays each have the same length as `nums`, contributing twice `O(n)` space, but this is still considered O(n) because constant factors are ignored in Big O notation.

Given this, the overall space complexity is also `O(n)` as the stack and the arrays `left` and `right` are linear in size to the input size `n`.

So, the code has a time complexity of `O(n)` and a space complexity of `O(n)`.

๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ