DSA Sum of Subarray Ranges

The problem

The range of a subarray is its maximum minus its minimum. The sum of subarray ranges adds that gap over every subarray of a list. A subarray is a contiguous run of elements.

A single-value subarray always has range zero. Wider subarrays contribute the spread between their extremes. The cases below are the ones this article solves.

cases = [
    ([1, 2, 3], 4),
    ([1, 3, 3], 4),
    ([4, -2, -3, 4, 1], 59),
    ([3, 3, 3], 0),
    ([7], 0),
]
for nums, expected in cases:
    print("nums", nums, "sum of ranges:", expected)

The third case mixes signs and reaches 59. The fourth case repeats one value, so every spread inside it is zero.

Intuition: list every subarray and measure its spread

The first idea writes out every subarray and adds its maximum minus its minimum. On a three-value list the full list is short enough to print. Every row below is one term of the sum.

nums = [1, 2, 3]
total = 0
for i in range(len(nums)):
    for j in range(i, len(nums)):
        sub = nums[i:j + 1]
        spread = max(sub) - min(sub)
        total += spread
        print(sub, "max:", max(sub), "min:", min(sub), "range:", spread)
print("total:", total)

Six rows give 4, and the three single-value rows give nothing. The idea is sound and hopeless at scale. The row count grows with the square of the length.

Brute force: extend and track both extremes

The brute force keeps the enumeration and tracks the running minimum and maximum together. Each start position extends one step at a time. A counter records the subarrays rated.

def brute_ranges(nums):
    total = 0
    subs = 0
    for i in range(len(nums)):
        low = nums[i]
        high = nums[i]
        for j in range(i, len(nums)):
            low = min(low, nums[j])
            high = max(high, nums[j])
            total += high - low
            subs += 1
    return total, subs

for nums in [[1, 2, 3], [1, 3, 3], [4, -2, -3, 4, 1]]:
    total, subs = brute_ranges(nums)
    print("nums", nums, "total:", total, "subarrays rated:", subs)

The totals agree with the cases, including 59 on the mixed-sign list. The rated count is again the full subarray count. The split in the next section is what removes it.

The optimal solution: maximums minus minimums

Summing the ranges splits into summing the maximums and subtracting the sum of the minimums, because each subarray's range is a difference and a sum of differences is a difference of sums. That one split is the whole method.

The minimum half is the boundary machine from the sum-of-subarray-minimums lesson. Each element contributes its value times its left choices times its right choices, with one strict side so duplicates are counted once.

The maximum half needs no new machine. Negating every value turns maximums into minimums of the negated list. Running the same machine on the negated list and negating its total gives the sum of maximums, with the strict side mirrored for free.

def sum_mins(nums):
    n = len(nums)
    left = [0] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        previous = stack[-1] if stack else -1
        left[i] = i - previous
        stack.append(i)
    right = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        following = stack[-1] if stack else n
        right[i] = following - i
        stack.append(i)
    total = 0
    for i in range(n):
        total += nums[i] * left[i] * right[i]
    return total


def sum_ranges(nums):
    mins = sum_mins(nums)
    maxs = -sum_mins([-value for value in nums])
    return maxs - mins

cases = [
    ([1, 2, 3], 4),
    ([1, 3, 3], 4),
    ([4, -2, -3, 4, 1], 59),
    ([3, 3, 3], 0),
    ([7], 0),
]
for nums, expected in cases:
    mins = sum_mins(nums)
    maxs = -sum_mins([-value for value in nums])
    result = sum_ranges(nums)
    print("nums", nums, "- max sum:", maxs, "min sum:", mins, "ranges:", result, "expected:", expected, "match:", result == expected)

All five cases pass. The duplicate list [1, 3, 3] gives 16 minus 12. Both halves stay consistent on equal values because the same strictness rule runs on both, once directly and once negated.

Walkthrough: both tables for [1, 2, 3]

The table prints one row per element. Each element carries a minimum contribution and a maximum contribution, computed from its own pair of boundaries. The totals sit at the bottom.

def contributions(nums, want_max):
    parts = []
    n = len(nums)
    for i in range(n):
        left = 1
        j = i - 1
        while j >= 0 and (nums[j] <= nums[i] if want_max else nums[j] >= nums[i]):
            left += 1
            j -= 1
        right = 1
        j = i + 1
        while j < n and (nums[j] < nums[i] if want_max else nums[j] > nums[i]):
            right += 1
            j += 1
        parts.append((nums[i], left, right, nums[i] * left * right))
    return parts

nums = [1, 2, 3]
min_parts = contributions(nums, False)
max_parts = contributions(nums, True)
print("value | min left | min right | min part | max left | max right | max part")
for low, high in zip(min_parts, max_parts):
    print(low[0], "|", low[1], "|", low[2], "|", low[3], "|", high[1], "|", high[2], "|", high[3])
print("min sum:", sum(part[3] for part in min_parts), " max sum:", sum(part[3] for part in max_parts))
print("ranges:", sum(part[3] for part in max_parts) - sum(part[3] for part in min_parts))

The value 3 leads the maximum side with nine. It is the largest value of three subarrays and the only value of its own. The subtraction at the bottom reads the answer straight off the two totals.

Complexity

The brute force rates every subarray, so its time is O(n^2) and its extra space is O(1). The split runs the stack machine twice, so its time is O(n) and its extra space is O(n).

The counts below run counted stack passes on a fixed pattern of values. The machine runs once on the list and once on its negation, so the operations column covers both runs.

def counted_mins(nums):
    n = len(nums)
    operations = 0
    left = [0] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
            operations += 1
        previous = stack[-1] if stack else -1
        left[i] = i - previous
        stack.append(i)
        operations += 1
    right = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
            operations += 1
        following = stack[-1] if stack else n
        right[i] = following - i
        stack.append(i)
        operations += 1
    return operations

for n in [5, 50, 500]:
    nums = [(i * 37) % 91 - 45 for i in range(n)]
    operations = counted_mins(nums) + counted_mins([-value for value in nums])
    subarrays = n * (n + 1) // 2
    print("values:", n, "- subarrays rated:", subarrays, " stack operations, both runs:", operations)

At 500 values the brute force rates 125,250 subarrays. Two stack runs together spend a few thousand operations. Splitting one hard sum into two known sums is the whole win.

Edge cases and pitfalls

An empty list sums to zero. A single value has range zero by definition. A list of one repeated value also sums to zero, because the maximum sum and the minimum sum come out equal.

def sum_mins(nums):
    n = len(nums)
    left = [0] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        previous = stack[-1] if stack else -1
        left[i] = i - previous
        stack.append(i)
    right = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        following = stack[-1] if stack else n
        right[i] = following - i
        stack.append(i)
    total = 0
    for i in range(n):
        total += nums[i] * left[i] * right[i]
    return total


def sum_ranges(nums):
    mins = sum_mins(nums)
    maxs = -sum_mins([-value for value in nums])
    return maxs - mins

print("empty list:", sum_ranges([]))
print("single value:", sum_ranges([7]))
print("all equal:", sum_ranges([3, 3, 3]))
print("two values:", sum_ranges([2, 1]))
print("negatives:", sum_ranges([-2, -5]))

The pitfall is feeding the maximum half through the machine without flipping anything. The comparisons stay pointed at minimums, the two halves come out identical, and every list reports zero.

def sum_mins(nums):
    n = len(nums)
    left = [0] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        previous = stack[-1] if stack else -1
        left[i] = i - previous
        stack.append(i)
    right = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        following = stack[-1] if stack else n
        right[i] = following - i
        stack.append(i)
    total = 0
    for i in range(n):
        total += nums[i] * left[i] * right[i]
    return total

nums = [1, 2, 3]
print("minimums counted as maximums, ranges:", sum_mins(nums) - sum_mins(nums))
print("with negation, ranges:", -sum_mins([-value for value in nums]) - sum_mins(nums))