LeetCode Solutions Blog

Sum of Subarray Ranges

Number: 2227

Difficulty: Medium

Paid? No

Problem Description

Given an integer array nums, the range of a subarray is defined as the difference between the maximum and minimum element within that subarray. The task is to compute the sum of the ranges of all possible contiguous non-empty subarrays of nums.

Key Insights

Instead of enumerating all subarrays (which is O(n²)), calculate the contribution of each element as the maximum and minimum in subarrays.
Use monotonic stacks to compute, for each element, the number of subarrays where it is the minimum and where it is the maximum.
Specifically, determine the distance to previous and next less elements (for minimum) and previous and next greater elements (for maximum).
The overall sum is the aggregated difference of the contributions: (element * count_as_max) - (element * count_as_min).

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We solve the problem by breaking it into two parts: calculating the total contribution when each element acts as the maximum and as the minimum in subarrays. For each index i:

Compute left and right boundaries indicating how far we can extend while keeping nums[i] as the unique maximum or minimum using monotonic stacks.
Multiply these boundaries to determine the number of subarrays in which nums[i] is the maximum or minimum.
Accumulate the aggregate sum by adding nums[i] * (number of subarrays where it is maximum) and subtracting nums[i] * (number of subarrays where it is minimum).

This approach leverages monotonic stacks to avoid an O(n²) enumeration, delivering an O(n) time solution.

Code Solutions

def subArrayRanges(nums):
    n = len(nums)
    # Initialize arrays to store distance contributions for min and max
    left_min = [0] * n
    right_min = [0] * n
    left_max = [0] * n
    right_max = [0] * n

    # Compute left_min: distance to previous less element (strictly less)
    stack = []
    for i in range(n):
        # Maintain an increasing stack for minimums
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        left_min[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    # Compute right_min: distance to next less or equal element
    stack = []
    for i in range(n - 1, -1, -1):
        # Use >= to handle duplicates correctly
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        right_min[i] = stack[-1] - i if stack else n - i
        stack.append(i)

    # Compute left_max: distance to previous greater element (strictly greater)
    stack = []
    for i in range(n):
        # Maintain a decreasing stack for maximums
        while stack and nums[stack[-1]] < nums[i]:
            stack.pop()
        left_max[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    # Compute right_max: distance to next greater or equal element
    stack = []
    for i in range(n - 1, -1, -1):
        # Use <= to handle duplicates correctly
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        right_max[i] = stack[-1] - i if stack else n - i
        stack.append(i)

    # Calculate the final answer using contributions from max and min roles
    total = 0
    for i in range(n):
        total += nums[i] * left_max[i] * right_max[i]
        total -= nums[i] * left_min[i] * right_min[i]
    return total

# Example usage:
print(subArrayRanges([1, 2, 3]))  # Output: 4