DSA Sum of Subarray Minimums

The problem

A subarray is a contiguous run of elements. The sum of subarray minimums adds the smallest value of every subarray of a list. A list of n values holds n times n plus 1, divided by 2, subarrays.

Every subarray contributes exactly one minimum. The cases below are the ones this article solves.

cases = [
    ([3, 1, 2, 4], 17),
    ([2, 2], 6),
    ([2, 2, 1], 9),
    ([5, 4, 3, 2, 1], 35),
    ([1], 1),
]
for nums, expected in cases:
    print("nums", nums, "sum of minimums:", expected)

The second case is the trap in miniature. Its three subarrays are [2], [2] and [2, 2], and the shared pair must be counted once, not twice.

Intuition: list every subarray and take its smallest

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

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

Ten rows give 17. The idea is sound and hopeless at scale. The row count grows with the square of the length, and each row costs a scan of its own.

Brute force: extend and track the running minimum

The brute force keeps the enumeration but drops the repeated scanning. Each start position extends one step at a time and carries the smallest value seen on the way. A counter records the subarrays rated.

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

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

The totals agree with the cases. The rated count is the full subarray count every time. Nothing about a clever minimum tracker changes how many subarrays exist.

The optimal solution: count each element's family

Each element is the minimum of one family of subarrays, and the family size is its left choices times its right choices, where the boundaries are the nearest smaller value on the left and the nearest smaller-or-equal value on the right. That one sentence is the whole method.

A left choice is a start position the subarray may use without crossing the left boundary. A right choice is an end position with the same freedom. The element contributes its value times the family size.

The strictness sits on one side only. The left scan stops at a strictly smaller value, and the right scan stops at a smaller-or-equal value. Equal values then divide their shared subarrays between them instead of double counting. A monotonic stack, a stack whose values keep one order, finds both boundaries for all elements in one pass each.

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

cases = [
    ([3, 1, 2, 4], 17),
    ([2, 2], 6),
    ([2, 2, 1], 9),
    ([5, 4, 3, 2, 1], 35),
    ([1], 1),
]
for nums, expected in cases:
    result = sum_mins(nums)
    print("nums", nums, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. The duplicate case gives 6, so the shared subarray [2, 2] is counted exactly once across the two families.

Walkthrough: the boundary table for two lists

The table prints one row per element. The left and right columns are the choice counts from the two boundary scans. The contribution column multiplies value, left and right.

def table(nums):
    n = len(nums)
    total = 0
    print("value | left | right | contribution")
    for i in range(n):
        left = 1
        j = i - 1
        while j >= 0 and nums[j] >= nums[i]:
            left += 1
            j -= 1
        right = 1
        j = i + 1
        while j < n and nums[j] > nums[i]:
            right += 1
            j += 1
        part = nums[i] * left * right
        total += part
        print(nums[i], "|", left, "|", right, "|", part)
    print("total:", total)

print("first list [3, 1, 2, 4]")
table([3, 1, 2, 4])
print("second list [2, 2, 1]")
table([2, 2, 1])

The value 1 in the first list leads six subarrays, so it contributes 6 of the 17. In the second list the two equal values take one and two left choices. Their families stay disjoint, and the total still matches the brute force.

Complexity

The brute force rates every subarray, so its time is O(n^2) and its extra space is O(1). The stack passes push and pop each index at most once per pass, so the optimal time is O(n) and its extra space is O(n).

The counts below run a counted stack pass on falling lists, the worst shape for boundary scans. The subarray column is the brute force's rating count at the same sizes.

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 = list(range(n, 0, -1))
    subarrays = n * (n + 1) // 2
    print("values:", n, "- subarrays rated:", subarrays, " stack operations:", counted_mins(nums))

At 500 values the brute force rates 125,250 subarrays. The stack spends at most four operations per value across both passes. The family idea trades a square for a line.

Edge cases and pitfalls

An empty list has no subarrays and sums to zero. A single value sums to itself. Negative values need no special handling, because boundaries compare values, not sizes.

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

print("empty list:", sum_mins([]))
print("single value:", sum_mins([7]))
print("all equal:", sum_mins([2, 2, 2]))
print("negatives:", sum_mins([-1, -2]))

The pitfall is strictness on both sides. When both scans stop at equal values, a shared subarray belongs to no family and vanishes from the sum.

def sum_mins_both_strict(nums):
    total = 0
    n = len(nums)
    for i in range(n):
        left = 1
        j = i - 1
        while j >= 0 and nums[j] > nums[i]:
            left += 1
            j -= 1
        right = 1
        j = i + 1
        while j < n and nums[j] > nums[i]:
            right += 1
            j += 1
        total += nums[i] * left * right
    return total

print("both sides strict on [2, 2]:", sum_mins_both_strict([2, 2]))
print("correct total on [2, 2]: 6")