2832. Maximal Range That Each Element Is Maximum in It

MediumStackArrayMonotonic Stack
Leetcode Link

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].

Learn more about Stack and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

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.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

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].

  4. Calculate the Answer:

    • 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.

Solution Implementation

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
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
62        return answer;
63    }
64}
65
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
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
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

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).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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 👨‍🏫