LeetCode 2104 - Sum of Subarray Ranges

The problem gives us an integer array nums, and asks us to compute the sum of the ranges of every possible non-empty contiguous subarray. The range of a subarray is defined as: For every possible subarray, we calculate its range, then add all of those ranges together.

leetcodemediumarraystackmonotonic-stack

LeetCode Problem 2104

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

LeetCode 2104 - Sum of Subarray Ranges

Problem Understanding

The problem gives us an integer array nums, and asks us to compute the sum of the ranges of every possible non-empty contiguous subarray.

The range of a subarray is defined as:

maximum element - minimum element

For every possible subarray, we calculate its range, then add all of those ranges together.

For example, if:

nums = [1,2,3]

The subarrays are:

[1]       -> range = 0
[2]       -> range = 0
[3]       -> range = 0
[1,2]     -> range = 1
[2,3]     -> range = 1
[1,2,3]   -> range = 2

The final answer is:

0 + 0 + 0 + 1 + 1 + 2 = 4

The input array can contain both positive and negative integers. The array length is at most 1000, which means a quadratic solution is acceptable for the original constraints, but the follow-up explicitly asks for an O(n) solution.

The key challenge is that the number of subarrays is O(n²). If we compute the minimum and maximum separately for every subarray, the total complexity can become O(n³), which is inefficient.

Several edge cases are important:

  • Arrays with all equal values, because every subarray range becomes 0
  • Arrays containing negative numbers
  • Arrays with duplicate values, because monotonic stack logic must carefully avoid double counting
  • Very small arrays such as length 1
  • Strictly increasing or strictly decreasing arrays, because they create extreme stack behavior

The problem guarantees:

  • nums is non-empty
  • Values fit within signed 32-bit integers
  • The final answer may exceed 32-bit integer range, so larger integer types are necessary

Approaches

Brute Force Approach

The most straightforward solution is to enumerate every subarray.

For each starting index, we expand the subarray one element at a time while maintaining the current minimum and maximum values. The range for the current subarray is:

current_max - current_min

We add this value to the answer.

A naive brute force solution would recompute the minimum and maximum for every subarray independently, leading to O(n³) complexity. However, we can optimize slightly by updating the running minimum and maximum incrementally while expanding the subarray. That reduces the complexity to O(n²).

This works because every subarray is examined exactly once, and its range is computed correctly.

Although O(n²) passes for the given constraints, it does not satisfy the follow-up requirement of linear time.

Optimal Approach Using Monotonic Stacks

The key insight is that:

sum of subarray ranges
=
(sum of all subarray maximums)
-
(sum of all subarray minimums)

Instead of evaluating every subarray individually, we calculate how much each element contributes as:

  • a maximum
  • a minimum

For a particular element nums[i], we determine:

  • how many subarrays use it as the maximum
  • how many subarrays use it as the minimum

If an element appears as the maximum in k subarrays, then its total contribution to the maximum sum is:

nums[i] * k

Similarly for minimums.

To count these efficiently, we use monotonic stacks to find:

  • Previous Less Element
  • Next Less Element
  • Previous Greater Element
  • Next Greater Element

These boundaries determine how many subarrays can extend left and right while keeping the current element as the minimum or maximum.

This transforms the problem into a linear-time contribution counting problem.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Expands every subarray while tracking min and max
Optimal O(n) O(n) Uses monotonic stacks to count contributions

Algorithm Walkthrough

Step 1: Convert the Problem Into Contribution Counting

Instead of directly computing every subarray range, rewrite the formula as:

sum(maximums) - sum(minimums)

This allows us to process maximum contributions and minimum contributions independently.

Step 2: Count Minimum Contributions

For each index i, determine how many subarrays have nums[i] as their minimum value.

We need two boundaries:

  1. The nearest smaller element on the left
  2. The nearest smaller or equal element on the right

These boundaries ensure duplicates are handled correctly without double counting.

If:

left = distance to previous smaller
right = distance to next smaller-or-equal

then the number of subarrays where nums[i] is the minimum is:

left * right

Its contribution becomes:

nums[i] * left * right

We use a monotonic increasing stack to compute these boundaries efficiently.

Step 3: Count Maximum Contributions

Repeat the same process for maximums.

Now we use:

  • previous greater element
  • next greater or equal element

We maintain a monotonic decreasing stack.

Again:

count = left * right

Contribution:

nums[i] * left * right

Step 4: Compute Final Answer

The final answer is:

total_maximum_contribution - total_minimum_contribution

Why it works

Every subarray has exactly one maximum and one minimum. Instead of enumerating subarrays directly, we count how many subarrays each element dominates as the maximum or minimum.

The monotonic stack guarantees that for every element, we correctly identify the maximal interval where it remains the minimum or maximum. Multiplying the number of valid left choices by the number of valid right choices gives the exact number of subarrays contributed by that element.

Because every subarray contributes exactly once to the maximum sum and exactly once to the minimum sum, subtracting the totals produces the correct answer.

Python Solution

from typing import List

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)

        def sum_subarray_mins() -> int:
            stack = []
            result = 0

            for i in range(n + 1):
                current = nums[i] if i < n else float('-inf')

                while stack and nums[stack[-1]] > current:
                    mid = stack.pop()

                    left = mid - (stack[-1] if stack else -1)
                    right = i - mid

                    result += nums[mid] * left * right

                stack.append(i)

            return result

        def sum_subarray_maxs() -> int:
            stack = []
            result = 0

            for i in range(n + 1):
                current = nums[i] if i < n else float('inf')

                while stack and nums[stack[-1]] < current:
                    mid = stack.pop()

                    left = mid - (stack[-1] if stack else -1)
                    right = i - mid

                    result += nums[mid] * left * right

                stack.append(i)

            return result

        return sum_subarray_maxs() - sum_subarray_mins()

The implementation separates the computation into two helper functions:

  • sum_subarray_mins
  • sum_subarray_maxs

Each helper computes the total contribution of all elements when acting as either the minimum or maximum.

The stack stores indices rather than values because we need distances between positions. The stack maintains monotonic order:

  • Increasing order for minimums
  • Decreasing order for maximums

A sentinel iteration at n forces all remaining elements out of the stack so their contributions are processed.

When an index is popped:

left = mid - previous_index
right = next_index - mid

The number of subarrays where this element dominates is:

left * right

The contribution formula:

nums[mid] * left * right

adds the element's total effect across all valid subarrays.

Finally, subtracting the minimum contribution sum from the maximum contribution sum produces the answer.

Go Solution

func subArrayRanges(nums []int) int64 {
	n := len(nums)

	sumSubarrayMins := func() int64 {
		stack := []int{}
		var result int64 = 0

		for i := 0; i <= n; i++ {
			current := -(1 << 60)

			if i < n {
				current = nums[i]
			}

			for len(stack) > 0 && nums[stack[len(stack)-1]] > current {
				mid := stack[len(stack)-1]
				stack = stack[:len(stack)-1]

				leftBoundary := -1
				if len(stack) > 0 {
					leftBoundary = stack[len(stack)-1]
				}

				left := mid - leftBoundary
				right := i - mid

				result += int64(nums[mid]) * int64(left) * int64(right)
			}

			stack = append(stack, i)
		}

		return result
	}

	sumSubarrayMaxs := func() int64 {
		stack := []int{}
		var result int64 = 0

		for i := 0; i <= n; i++ {
			current := 1 << 60

			if i < n {
				current = nums[i]
			}

			for len(stack) > 0 && nums[stack[len(stack)-1]] < current {
				mid := stack[len(stack)-1]
				stack = stack[:len(stack)-1]

				leftBoundary := -1
				if len(stack) > 0 {
					leftBoundary = stack[len(stack)-1]
				}

				left := mid - leftBoundary
				right := i - mid

				result += int64(nums[mid]) * int64(left) * int64(right)
			}

			stack = append(stack, i)
		}

		return result
	}

	return sumSubarrayMaxs() - sumSubarrayMins()
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is integer handling. The result can exceed 32-bit integer range, so the function returns int64, and all contribution calculations are explicitly converted to int64.

Go does not provide built-in infinity values for integers, so large sentinel values are manually chosen:

-(1 << 60)
1 << 60

Slices are used as stacks with append and truncation operations.

Worked Examples

Example 1

nums = [1,2,3]

Maximum Contributions

Index Value Previous Greater Next Greater Left Choices Right Choices Contribution
0 1 -1 1 1 1 1
1 2 -1 2 2 1 4
2 3 -1 3 3 1 9

Total maximum sum:

1 + 4 + 9 = 14

Minimum Contributions

Index Value Previous Smaller Next Smaller Left Choices Right Choices Contribution
0 1 -1 3 1 3 3
1 2 0 3 1 2 4
2 3 1 3 1 1 3

Total minimum sum:

3 + 4 + 3 = 10

Final answer:

14 - 10 = 4

Example 2

nums = [1,3,3]

Maximum Contributions

Index Value Contribution
0 1 1
1 3 12
2 3 5

Total maximum sum:

18

Minimum Contributions

Index Value Contribution
0 1 3
1 3 6
2 3 5

Total minimum sum:

14

Final answer:

18 - 14 = 4

Example 3

nums = [4,-2,-3,4,1]

The algorithm computes:

sum(maximums) = 59 + sum(minimums)

After processing all stack contributions:

final answer = 59

The important aspect of this example is handling:

  • Negative numbers
  • Duplicate maximums
  • Mixed increasing and decreasing patterns

The monotonic stack correctly processes all of them in linear time.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every index is pushed and popped at most once in each stack
Space O(n) The monotonic stack may store all indices

The critical observation is that each element enters and leaves the stack only once. Although there are nested loops, the total number of stack operations across the entire algorithm is linear.

This is a standard amortized analysis for monotonic stack problems.

Test Cases

from typing import List

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)

        def sum_subarray_mins():
            stack = []
            result = 0

            for i in range(n + 1):
                current = nums[i] if i < n else float('-inf')

                while stack and nums[stack[-1]] > current:
                    mid = stack.pop()

                    left = mid - (stack[-1] if stack else -1)
                    right = i - mid

                    result += nums[mid] * left * right

                stack.append(i)

            return result

        def sum_subarray_maxs():
            stack = []
            result = 0

            for i in range(n + 1):
                current = nums[i] if i < n else float('inf')

                while stack and nums[stack[-1]] < current:
                    mid = stack.pop()

                    left = mid - (stack[-1] if stack else -1)
                    right = i - mid

                    result += nums[mid] * left * right

                stack.append(i)

            return result

        return sum_subarray_maxs() - sum_subarray_mins()

sol = Solution()

assert sol.subArrayRanges([1,2,3]) == 4          # basic increasing example
assert sol.subArrayRanges([1,3,3]) == 4          # duplicates
assert sol.subArrayRanges([4,-2,-3,4,1]) == 59  # mixed positive and negative

assert sol.subArrayRanges([1]) == 0              # single element
assert sol.subArrayRanges([5,5,5]) == 0          # all equal values

assert sol.subArrayRanges([1,2]) == 1            # simple increasing pair
assert sol.subArrayRanges([2,1]) == 1            # simple decreasing pair

assert sol.subArrayRanges([-1,-2,-3]) == 4       # all negative numbers

assert sol.subArrayRanges([1,2,3,4]) == 10       # strictly increasing
assert sol.subArrayRanges([4,3,2,1]) == 10       # strictly decreasing

assert sol.subArrayRanges([10,-10,10]) == 60     # large swings in range

Test Summary

Test Why
[1,2,3] Basic increasing example
[1,3,3] Validates duplicate handling
[4,-2,-3,4,1] Mixed positive and negative values
[1] Smallest possible input
[5,5,5] All ranges should be zero
[1,2] Small increasing pair
[2,1] Small decreasing pair
[-1,-2,-3] Negative number handling
[1,2,3,4] Strictly increasing sequence
[4,3,2,1] Strictly decreasing sequence
[10,-10,10] Large range differences

Edge Cases

Single Element Array

If the array contains only one element, the only subarray is the element itself. Since the minimum and maximum are equal, the range is always zero.

This can easily cause off-by-one mistakes in stack boundary calculations. The implementation handles it correctly because:

left = 1
right = 1

and the maximum and minimum contributions cancel out.

Arrays With Duplicate Values

Duplicate values are one of the most error-prone parts of monotonic stack problems.

If both sides use strict comparisons, some subarrays may be counted multiple times. If both use non-strict comparisons, some subarrays may never be counted.

The implementation carefully mixes strict and non-strict comparisons so each subarray is assigned to exactly one representative element.

This guarantees correctness without double counting.

Strictly Increasing or Decreasing Arrays

Monotonic arrays produce the deepest possible stack behavior.

For example:

[1,2,3,4,5]

creates a continuously increasing stack for minimum calculations.

A poorly designed algorithm might degrade into quadratic behavior. However, in this implementation, each index is still pushed and popped only once, so the total complexity remains linear.

Negative Numbers

Since ranges depend on differences between maximum and minimum values, negative numbers must be handled carefully.

For example:

[-3,-2,-1]

still has positive ranges because:

max - min

remains positive.

The algorithm works correctly because it never relies on positivity, only on relative ordering between elements.