2104. Sum of Subarray Ranges

MediumStackArrayMonotonic Stack
Leetcode Link

Problem Description

The problem provides us with an integer array called nums. We need to calculate the sum of the ranges of all possible subarrays of this array. A subarray is defined as a contiguous non-empty sequence of elements within an array, and the range of a subarray is the difference between the largest (maximum) and smallest (minimum) element in the subarray. In other words, we have to find all the subarrays, determine the range for each one, and then sum these ranges to get the final result.

Intuition

To solve this problem efficiently, we need to think beyond the brute force approach, which would involve finding all possible subarrays and then calculating the range for each. Since the number of subarrays grows quadratically with the array size, this would lead to a time-consuming solution. Instead, we need an optimized approach.

The key insight is to count how many times each element of the array becomes a minimum and a maximum of a subarray. We can find this out by determining, for each element, the bounds (to the left and to the right) within which it is the minimum or maximum. These bounds can be found using the concept of "monotonic stacks", which are stacks that maintain elements in a either strictly increasing or decreasing order.

The provided solution defines a function f(nums), which uses a monotonic stack to calculate the sum of the product of the number of subarrays, where each element of nums is the maximum. It initializes two lists, left and right, that store the indices of the next smaller elements to the left and right, respectively. When traversing the array, we maintain a stack that keeps track of the indices of elements in a non-decreasing order. If the current element is greater than the element at the top of the stack, we pop elements from the stack until we find an element smaller or the stack becomes empty. This process helps us locate the bounds for each element where it stands as the maximum.

Once we have the left and right arrays, we can calculate the sum of products of differences of indices and the value at each index.

For the minimum case, we invert the nums array by negating each element and pass it to the same function f. The inversion swaps the roles of maximum and minimum elements within the subarrays.

Finally, we sum up the maximums and minimums to get the total sum of subarray ranges. This approach is efficient because each element is pushed and popped from the stack only once, making it an O(n) solution, where n is the length of the array.

Learn more about Stack and Monotonic Stack patterns.

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

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The solution applies a technique using 'monotonic stacks' to calculate the sum of all subarray ranges efficiently. Here is how the implementation unfolds:

  1. Monotonic Stacks: We use two monotonic stacks to find the bounds within which each element is the maximum and minimum, respectively. A monotonic stack is a stack that is either strictly increasing or decreasing.

  2. Finding Left and Right Bounds:

    • For each element in nums, we find the nearest smaller element to the left and store its index in the left array. If there's no such element, we store -1.
    • Similarly, we find the nearest smaller element to the right for each element and store its index in the right array. If there's no such element, n (the length of nums) is stored.

  3. Calculating the Sum for Maximums:

    • We iterate through nums, using the indices in left and right to determine the number of subarrays where each element is the maximum.
    • The sum for each element as the maximum is calculated by multiplying the element's value by the difference between its index and its left bound and by the difference between its right bound and its index. This product represents the sum of ranges for the subarrays where this element is the maximum.

  4. Calculating the Sum for Minimums:

    • We negate each element in nums and repeat the above process. This effectively swaps the roles of the maximums and minimums without changing the range calculation logic.

  5. Combine Sums of Maximums and Minimums:

    • The function f(nums) calculates the sum assuming nums[i] is the maximum in its subarrays, while f([-v for v in nums]) calculates the sum assuming nums[i] is the minimum.
    • The overall solution is the sum of these two results, giving us the sum of all subarray ranges.

  6. Efficiency:

    • The algorithm is efficient because each element is pushed onto and popped from the stack only once. Since each element is dealt with in constant time when it is at the top of the stack, the total time complexity for the algorithm is O(n), where n is the number of elements in nums.

The code leverages the concept of calculating the contribution of each element to the sum of subarray ranges separately as a maximum and minimum, which allows for an elegant and efficient solution. It bypasses the need to enumerate every subarray explicitly, which would be computationally expensive for larger arrays.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach.

Consider the array nums = [3, 1, 2, 4]. We want to find the sum of the ranges of all possible subarrays.

  1. Monotonic Stacks: We will use monotonic stacks to find bounds for each element where it acts as the maximum and minimum of subarrays.

  2. Finding Left and Right Bounds:

    • For maximums, starting with an empty stack, we process each element in nums from left to right. Taking the first element 3, there is no smaller element to the left, so left[0] = -1. Our stack will be [3].
    • Moving to 1, it is smaller than 3, so for the maximum case, left[1] = -1. We update our stack to [1].
    • For 2, the nearest smaller element to the left is 1, so left[2] = 1. Our stack is now [1, 2].
    • Lastly for 4, there are no smaller elements to the left, so left[3] = -1, and our stack ends as [1, 2, 4].
    • To find the right bounds, we assume each element is the last element (right[i] = n, with n = 4). Hence, right = [4, 4, 4, 4] as no element in nums has a next smaller element on the right.

  3. Calculating the Sum for Maximums:

    • For 3, it is the maximum for subarrays using the elements [3], [3, 1], [3, 1, 2], [3, 1, 2, 4]. The sum of these subarray ranges is 3*1*4 = 12.
    • For 1, it is not the maximum for any subarrays; we can skip it for the maximum sum.
    • For 2, it is the maximum for subarrays [2] and [1, 2], with corresponding indices [2, 3]. The sum is 2*1*1 = 2.
    • For 4, it is the maximum for subarrays [4], [2, 4], and [1, 2, 4], which is a sum of 4*3*1 = 12.

  4. Calculating the Sum for Minimums:

    • We negate each element of nums to get [-3, -1, -2, -4] and repeat steps 2 and 3. For minimums, 4 and 3 never become the minimum of any subarrays.
    • -1 is the minimum for the subarrays [-1], [-3, -1], [-1, -2], [-3, -1, -2], [-1, -2, -4], [-3, -1, -2, -4], with sum -1*(1+2+1+2)*1 = -12.
    • -2 is the minimum for subarrays [-2], [-1, -2], [-2, -4], [-1, -2, -4], with sum -2*(1+2)*2 = -12.

  5. Combine Sums of Maximums and Minimums:

    • The sum of subarray ranges considering maximums from step 3 is 12 + 0 + 2 + 12 = 26.
    • The sum of subarray ranges considering minimums from step 4 is 0 + (-12) + (-12) + 0 = -24.
    • Adding these, we get 26 - 24 = 2.

  6. Efficiency:

    • During this example, each element was processed in constant time, showing how each element contributes to the sum with a single pass through the array without explicitly considering every subarray.

So the sum of the ranges of all possible subarrays of nums = [3, 1, 2, 4] is 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def subArrayRanges(self, nums: List[int]) -> int:
5        # Function to calculate the sum of maximum or minimum of all subarrays
6        def calculate_subarray_sums(nums):
7            # Initialize stack, left and right index arrays
8            stack = []
9            n = len(nums)
10            # Left index for the nearest smaller number to the left of the current number
11            left_indices = [-1] * n
12            # Right index for the nearest smaller number to the right of the current number
13            right_indices = [n] * n
14          
15            # Calculate the left indices
16            for i, value in enumerate(nums):
17                # If the stack is not empty and current element is greater
18                # pop elements from the stack
19                while stack and nums[stack[-1]] <= value:
20                    stack.pop()
21                # If stack is not empty assign the last element as the left limit
22                if stack:
23                    left_indices[i] = stack[-1]
24                # Push the current index onto the stack
25                stack.append(i)
26          
27            # Reset the stack for the right indices calculation
28            stack = []
29          
30            # Calculate the right indices
31            for i in range(n - 1, -1, -1):
32                # If the stack is not empty and current element is greater, pop from stack
33                while stack and nums[stack[-1]] < nums[i]:
34                    stack.pop()
35                # If stack is not empty, assign the last element as the right limit
36                if stack:
37                    right_indices[i] = stack[-1]
38                # Push the current index onto the stack
39                stack.append(i)
40          
41            # Calculate the final sum
42            return sum((i - left_indices[i]) * (right_indices[i] - i) * value for i, value in enumerate(nums))
43
44        # Calculate maximum values sum
45        max_sum = calculate_subarray_sums(nums)
46        # Calculate minimum values sum (inverting the values)
47        min_sum = calculate_subarray_sums([-value for value in nums])
48        # Return the total sum of all subarray ranges
49        return max_sum + min_sum
50
51# Example usage:
52# solution = Solution()
53# print(solution.subArrayRanges([1, 2, 3]))  # Output: 4
54
1import java.util.ArrayDeque;
2import java.util.Arrays;
3import java.util.Deque;
4
5class Solution {
6    public long subArrayRanges(int[] nums) {
7        // Calculate the sum of max elements in all subarrays
8        long sumOfMax = calculateSubarrayValues(nums);
9
10        // Invert all numbers in nums to find the sum of min elements using the same function
11        for (int i = 0; i < nums.length; ++i) {
12            nums[i] *= -1;
13        }
14        long sumOfMin = calculateSubarrayValues(nums);
15
16        // The total sum of subarray ranges is the sum of max elements plus the (inverted) sum of min elements
17        return sumOfMax + sumOfMin;
18    }
19
20    private long calculateSubarrayValues(int[] nums) {
21        Deque<Integer> stack = new ArrayDeque<>();
22        int n = nums.length;
23        int[] left = new int[n];
24        int[] right = new int[n];
25        Arrays.fill(left, -1);  // Initialize left bounds for all elements
26        Arrays.fill(right, n);  // Initialize right bounds for all elements
27
28        // Calculate the left bounds for each element
29        for (int i = 0; i < n; ++i) {
30            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
31                stack.pop();
32            }
33            if (!stack.isEmpty()) {
34                left[i] = stack.peek();
35            }
36            stack.push(i);
37        }
38
39        stack.clear(); // Clear the stack for the next phase of calculations
40
41        // Calculate the right bounds for each element
42        for (int i = n - 1; i >= 0; --i) {
43            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
44                stack.pop();
45            }
46            if (!stack.isEmpty()) {
47                right[i] = stack.peek();
48            }
49            stack.push(i);
50        }
51
52        long sum = 0; // Initialize the sum to aggregate the subarray values
53        // Calculate the sum of values using the left and right bounds
54        for (int i = 0; i < n; ++i) {
55            sum += (long) (i - left[i]) * (right[i] - i) * nums[i];
56        }
57      
58        // Return the total sum of subarray values for either max or min based on the nums state
59        return sum;
60    }
61}
62
1class Solution {
2public:
3    // Function to calculate the sum of ranges of all subarrays
4    long long subArrayRanges(vector<int>& nums) {
5        long long maxSum = calculateSum(nums); // Sum of max elements of all subarrays
6      
7        // Negate all the elements to use the same function for minimum
8        for (int i = 0; i < nums.size(); ++i) {
9            nums[i] *= -1;
10        }
11      
12        long long minSum = calculateSum(nums); // Sum of min elements of all subarrays
13        return maxSum + minSum; // Sum of ranges (max-min) of all subarrays
14    }
15
16    // Helper function to calculate the sum of either max or min elements of all subarrays
17    long long calculateSum(vector<int>& nums) {
18        stack<int> st; // Stack to maintain indices
19        int n = nums.size();
20        vector<int> left(n, -1); // Indices of previous smaller or equal elements
21        vector<int> right(n, n); // Indices of next smaller elements
22        long long sum = 0; // Resulting sum
23
24        // Fill left array with previous smaller or equal indices
25        for (int i = 0; i < n; ++i) {
26            while (!st.empty() && nums[st.top()] <= nums[i]) st.pop();
27            if (!st.empty()) left[i] = st.top();
28            st.push(i);
29        }
30      
31        // Clear stack to reuse it for the right array
32        st = stack<int>();
33
34        // Fill right array with next smaller indices
35        for (int i = n - 1; i >= 0; --i) {
36            while (!st.empty() && nums[st.top()] < nums[i]) st.pop();
37            if (!st.empty()) right[i] = st.top();
38            st.push(i);
39        }
40
41        // Calculate the sum based on the left and right arrays
42        for (int i = 0; i < n; ++i) {
43            sum += (long long) (i - left[i]) * (right[i] - i) * nums[i];
44        }
45
46        return sum; // Return the total sum for the array
47    }
48};
49
1function subArrayRanges(nums: number[]): number {
2    // Define the length of the nums array for later use.
3    const length = nums.length;
4    // This variable will store the cumulative sum of all subarray ranges.
5    let totalRangeSum = 0;
6
7    // Outer loop to consider starting point of subarrays.
8    for (let start = 0; start < length - 1; start++) {
9        // Initialize min and max with the first element of the current subarray.
10        let currentMin = nums[start];
11        let currentMax = nums[start];
12
13        // Inner loop to consider different ending points of subarrays.
14        for (let end = start + 1; end < length; end++) {
15            // Update the current minimum and maximum of the subarray.
16            currentMin = Math.min(currentMin, nums[end]);
17            currentMax = Math.max(currentMax, nums[end]);
18            // Add the range (max - min) of this subarray to the total sum.
19            totalRangeSum += currentMax - currentMin;
20        }
21    }
22
23    // Return the total sum of all ranges.
24    return totalRangeSum;
25}
26
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

The given code calculates the sum of the range of each subarray in an integer array. It defines a function f that computes the cumulative product of the value at each position, the distance to the closest smaller element on the left, and the distance to the closest smaller element on the right.

Time Complexity:

  1. The function f loops through the array twice - once in the forward direction and once in the reverse direction. In each loop, every element is processed only once, and each element is inserted and removed from the stack at most once. This leads to a time complexity of O(n) for each loop, where n is the length of the nums.

  2. The sum computation iterates over each element in nums once, executing a constant amount of work for each element. Thus, this also takes O(n) time.

  3. Since the function f is called twice - once for the original nums array and once for the negated values of nums, the total time complexity is O(2n), which simplifies to O(n).

Therefore, the overall time complexity of the subArrayRanges method is O(n).

Space Complexity:

  1. There are two additional arrays created, left and right, each of the same length as nums, leading to a space complexity of O(2n) which simplifies to O(n).

  2. Additionally, a stack is used to keep track of indices while iterating through the array. In the worst case, this stack could hold all n elements at once if the array is strictly monotonic. This does not increase the overall space complexity since it remains O(n).

  3. There are no recursive calls or additional data structures that grow with the size of the input beyond what has already been accounted for.

Hence, the overall space complexity for the subArrayRanges method is 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:

How many ways can you arrange the three letters A, B and C?

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