Solution Explanation for LeetCode 2104: Sum of Subarray Ranges

This problem asks to calculate the sum of ranges of all subarrays within a given integer array nums. The range of a subarray is the difference between its maximum and minimum elements. A brute-force approach would have O(n^3) time complexity, but we can achieve O(n) using a more efficient method.

Approach 1: Brute Force (O(n^3))

This approach directly implements the problem description. We iterate through all possible subarrays and calculate their ranges.

Code (Python):

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(n):
            for j in range(i, n):
                sub_array = nums[i:j+1]
                ans += max(sub_array) - min(sub_array)
        return ans
 

Time Complexity: O(n^3). The nested loops iterate through all subarrays, and finding the max and min within each subarray takes O(k) time for a subarray of length k. The sum of lengths of all subarrays is O(n^2), leading to overall O(n^3).

Space Complexity: O(1). We only use a few variables to store the current values.

Approach 2: Optimized Approach (O(n))

This approach leverages the concept of monotonic stacks to find the maximum and minimum elements efficiently for each element. Instead of recalculating the max and min for every subarray, we keep track of the range contribution each element makes.

Intuition: For each element, we need to know how many times it acts as the maximum (or minimum) within a subarray. We can find this using monotonic stacks that store indices.

Algorithm:

1. Calculate Contribution of Max:
   • Use a monotonic decreasing stack. For each element, pop elements from the stack that are smaller. The number of elements popped gives the number of subarrays where the current element is the maximum. This is because if an element x is popped, it means the current element is greater, making it the maximum in all subarrays containing x as well.
2. Calculate Contribution of Min:
   • Repeat step 1 with a monotonic increasing stack to find the number of times each element acts as the minimum in a subarray.
3. Combine Results: Sum up the total contribution.

Code (Python):

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        def calculate_contribution(nums, is_max):
            n = len(nums)
            stack = []
            contribution = [0] * n
            for i, num in enumerate(nums):
                while stack and nums[stack[-1]] < num if is_max else nums[stack[-1]] > num:
                    j = stack.pop()
                    k = stack[-1] if stack else -1
                    contribution[j] += (i - j) * (j - k) if is_max else (j - k) * (i - j)
                stack.append(i)
            while stack:
                j = stack.pop()
                k = stack[-1] if stack else -1
                contribution[j] += (n - j) * (j - k) if is_max else (j - k) * (n - j)
            return contribution
 
        max_contribution = calculate_contribution(nums, True)
        min_contribution = calculate_contribution(nums, False)
        ans = 0
        for i in range(len(nums)):
            ans += max_contribution[i] * nums[i] - min_contribution[i] * nums[i]
        return ans
 

Time Complexity: O(n). Each element is pushed and popped at most once from the stacks.

Space Complexity: O(n) for the stacks and contribution arrays.

The optimized approach (Approach 2) is significantly faster for larger input arrays because it avoids the nested loop structure of the brute-force approach. Therefore, it's the preferred solution. The code provided in Approach 2 is more complex but achieves the desired linear time complexity. The other language implementations (Java, C++, Go, TypeScript, Rust) would follow a similar logic using their respective stack and array structures.