Sum of Subarray Ranges

The most straightforward idea is to do exactly what the problem says: look at every possible subarray, find the biggest and smallest values inside it, subtract them, and add that difference to a running total.

A subarray is defined by its starting index i and ending index j (where j ≥ i). For each such pair (i, j), we scan through all elements from index i to index j to find the minimum and maximum. The difference (max − min) is the range for that subarray.

Think of it like reading a list of daily temperatures for every possible consecutive span of days. For each span, you look at every day in that span to find the hottest and coldest days, then note the difference. You repeat this for all possible spans.

Let's trace through with nums = [1, 2, 3]:

Step 1: Consider subarray [1] (i=0, j=0). Scan from index 0 to 0: min = 1, max = 1. Range = 1 - 1 = 0. Running total = 0.

Step 2: Consider subarray [1, 2] (i=0, j=1). Scan from index 0 to 1: compare 1 and 2. min = 1, max = 2. Range = 2 - 1 = 1. Running total = 0 + 1 = 1.

Step 3: Consider subarray [1, 2, 3] (i=0, j=2). Scan from index 0 to 2: compare 1, 2, and 3. min = 1, max = 3. Range = 3 - 1 = 2. Running total = 1 + 2 = 3.

Step 4: Consider subarray [2] (i=1, j=1). Scan: min = 2, max = 2. Range = 0. Running total stays at 3.

Step 5: Consider subarray [2, 3] (i=1, j=2). Scan index 1 to 2: min = 2, max = 3. Range = 3 - 2 = 1. Running total = 3 + 1 = 4.

Step 6: Consider subarray [3] (i=2, j=2). Scan: min = 3, max = 3. Range = 0. Running total stays at 4.

Result: The sum of all subarray ranges is 4.

Notice that for each subarray we performed a full scan to find the minimum and maximum. For the subarray [1, 2, 3] of length 3, we compared all three elements. This inner scan is what gives us the extra factor of n in the time complexity.

1. Initialize total = 0
2. For each starting index i from 0 to n-1:
   • For each ending index j from i to n-1:
     • Scan from index i to j to find the minimum and maximum
     • Add (maximum - minimum) to total
3. Return total

Time Complexity: O(n³)

The outer two loops enumerate all n × (n+1) / 2 subarrays. For each subarray of length L, the inner scan takes O(L) time. Summing over all subarrays, the total work is proportional to n³ / 6, which simplifies to O(n³).

Space Complexity: O(1)

We only use a few integer variables (total, mi, mx, loop counters). No additional data structures that grow with input size.

Instead of rescanning every subarray from scratch, we can be smarter. Fix a starting index i, and then extend the subarray one element at a time to the right. As we add each new element, we only need to check whether it is smaller than our current minimum or larger than our current maximum.

Imagine you are tracking the highest and lowest score in a growing list of exam results. Each time a new score arrives, you do not re-read the entire list — you simply compare the new score against your recorded high and low. If it beats either record, you update. This one comparison replaces a full scan of the list.

By maintaining running min and max variables, we eliminate the inner scan entirely, reducing the work per subarray from O(length) to O(1).

Let's trace through with nums = [1, 2, 3]:

Step 1: Start outer loop with i=0. Initialize current_min = nums[0] = 1 and current_max = nums[0] = 1. This is our baseline for all subarrays beginning at index 0.

Step 2: Extend to j=1, value nums[1] = 2. Update current_min = min(1, 2) = 1 (unchanged). Update current_max = max(1, 2) = 2 (new max). Range of [1, 2] = 2 - 1 = 1. Add to total: ans = 0 + 1 = 1.

Step 3: Extend to j=2, value nums[2] = 3. Update current_min = min(1, 3) = 1 (unchanged). Update current_max = max(1, 3) = 3 (new max). Range of [1, 2, 3] = 3 - 1 = 2. Add to total: ans = 1 + 2 = 3.

Step 4: Move to outer loop i=1. Initialize current_min = 2, current_max = 2. Now examining all subarrays starting at index 1.

Step 5: Extend to j=2, value nums[2] = 3. Update current_min = min(2, 3) = 2 (unchanged). Update current_max = max(2, 3) = 3 (new max). Range of [2, 3] = 3 - 2 = 1. Add to total: ans = 3 + 1 = 4.

Step 6: No more starting positions to process. Single-element subarrays [1], [2], [3] each have range 0 and were skipped since we start j from i+1. Final result: 4.

1. Initialize total = 0
2. For each starting index i from 0 to n-1:
   • Set current_min = nums[i] and current_max = nums[i]
   • For each ending index j from i+1 to n-1:
     • Update current_min = min(current_min, nums[j])
     • Update current_max = max(current_max, nums[j])
     • Add (current_max - current_min) to total
3. Return total

Time Complexity: O(n²)

The outer loop runs n times. For each starting index i, the inner loop runs up to n - i - 1 times. The total number of iterations is n × (n-1) / 2, which is O(n²). Each iteration does O(1) work (two comparisons and an addition), so the overall time is O(n²).

Compared to the brute force O(n³), we eliminated the inner scan by maintaining running min/max variables. This is a significant improvement — for n = 1000, we go from ~1.67 × 10⁸ operations down to ~5 × 10⁵.

Space Complexity: O(1)

We only use a constant number of variables regardless of input size.

The previous approaches compute the range (max − min) for each subarray individually. The optimal approach rearranges the entire computation.

Consider what the "sum of all subarray ranges" really means:

sum of ranges = Σ (max of subarray − min of subarray) for every subarray

We can split this into two independent sums:

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

Now we have two separate problems:

1. Compute the sum of the maximum element across all subarrays
2. Compute the sum of the minimum element across all subarrays

For each of these, we flip the question from "what is the max/min of subarray [i..j]?" to "for element nums[k], how many subarrays have nums[k] as their maximum (or minimum)?" If we can answer this for every element, we simply multiply each element by its count and sum up.

To count how many subarrays have nums[k] as their minimum, we need to find the nearest smaller element on the left and on the right. The region between these two boundaries defines the set of subarrays where nums[k] is the smallest. A monotonic stack finds these boundaries in O(n) total time.

The same logic applies for maximums, using a monotonic stack that tracks the nearest larger elements instead.

Think of it like a mountain range. For each valley (local minimum), we ask: how far left and right can we extend a window before hitting a deeper valley? The number of windows where this valley is the lowest point equals left_distance × right_distance. Similarly, for each peak (local maximum), we ask: how far can we extend before hitting a taller peak?

Let's trace through with nums = [1, 3, 3]:

We decompose the problem: sum of ranges = (sum of subarray maximums) − (sum of subarray minimums). We compute each using a monotonic stack that processes elements left to right and calculates contributions when elements are popped.

Pass 1: Computing Sum of Subarray Minimums (min_sum)

We maintain a monotonic increasing stack (values increase from bottom to top). When we process all elements, remaining stack entries are cleaned up using n as the right boundary. Each popped element's contribution = value × (distance to left boundary) × (distance to right boundary).

Step 1: Initialize empty stack. min_sum = 0.

Step 2: Process nums[0] = 1. Stack is empty, so push value 1 (index 0). Stack: [1].

Step 3: Process nums[1] = 3. Since 3 > stack top (1), increasing order holds. Push value 3 (index 1). Stack: [1, 3].

Step 4: Process nums[2] = 3. Since 3 is not strictly greater than stack top (3), order holds. Push value 3 (index 2). Stack: [1, 3, 3].

Step 5: All elements processed. Clean up stack. Pop 3 (index 2): right boundary = n = 3, left boundary = index 1 (new stack top). This 3 is the minimum of (3−2) × (2−1) = 1 subarray: [3] at position 2. min_sum += 3 × 1 = 3.

Step 6: Pop 3 (index 1): right = 3, left = index 0 (stack top). Minimum in (3−1) × (1−0) = 2 subarrays: [3] at position 1, and [3,3]. min_sum += 3 × 2 = 6. Total min_sum = 9.

Step 7: Pop 1 (index 0): right = 3, left = −1 (stack empty). Minimum in (3−0) × (0+1) = 3 subarrays: [1], [1,3], and [1,3,3]. min_sum += 1 × 3 = 3. Total min_sum = 12.

Pass 2: Computing Sum of Subarray Maximums (max_sum)

We use a monotonic decreasing stack. When we encounter a larger element, we pop and calculate the popped element's contribution as a maximum.

Step 8: Begin Pass 2. Initialize empty stack, max_sum = 0. Process nums[0] = 1. Stack empty, push value 1 (index 0). Stack: [1].

Step 9: Process nums[1] = 3. Since 3 > stack top (1), pop! Value 1 (index 0): right = 1, left = −1 (stack empty). Maximum in (1−0) × (0+1) = 1 subarray: [1]. max_sum += 1 × 1 = 1.

Step 10: Push value 3 (index 1). Stack: [3].

Step 11: Process nums[2] = 3. Since 3 is not strictly greater than stack top (3), push value 3 (index 2). Stack: [3, 3].

Step 12: Clean up. Pop 3 (index 2): right = 3, left = index 1 (stack top). Maximum in (3−2) × (2−1) = 1 subarray: [3] at position 2. max_sum += 3 × 1 = 3. Total max_sum = 4.

Step 13: Pop 3 (index 1): right = 3, left = −1 (stack empty). Maximum in (3−1) × (1+1) = 4 subarrays: [3] at position 1, [1,3], [3,3], and [1,3,3]. max_sum += 3 × 4 = 12. Total max_sum = 16. Final result = max_sum − min_sum = 16 − 12 = 4.

1. Initialize result = 0
2. Pass 1 — Subtract sum of subarray minimums:
   • Create an empty stack (stores indices)
   • For i from 0 to n (inclusive):
     • While stack is not empty AND (i == n OR nums[stack.top()] > nums[i]):
       • Pop index j from stack
       • Let left = stack.top() if stack is not empty, else −1
       • Subtract nums[j] × (i − j) × (j − left) from result
     • Push i onto stack
3. Pass 2 — Add sum of subarray maximums:
   • Clear the stack
   • For i from 0 to n (inclusive):
     • While stack is not empty AND (i == n OR nums[stack.top()] < nums[i]):
       • Pop index j from stack
       • Let left = stack.top() if stack is not empty, else −1
       • Add nums[j] × (i − j) × (j − left) to result
     • Push i onto stack
4. Return result

Time Complexity: O(n)

Each of the two passes iterates through n+1 indices. Within each pass, every element is pushed onto the stack exactly once and popped at most once. Since each push and pop is O(1), the total work per pass is O(n). Two passes give O(2n) = O(n).

This is a dramatic improvement over O(n²). For n = 1000, we perform roughly 2000 operations instead of 500,000. For n = 10⁵, the difference is even more stark: 200,000 vs 5 × 10⁹.

Space Complexity: O(n)

The monotonic stack can hold at most n elements at any point (in the worst case of a sorted array, all elements are pushed before any are popped). We use one stack per pass, cleared between passes, so the peak space usage is O(n).