Abstract / Summary

Compute the sum of differences between maximum and minimum elements for every possible subarray in a list of numbers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Monotonic Stack
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method subArrayRanges. The method receives a list of integers and returns the sum of the ranges (maximum minus minimum) of every contiguous sub-array. The algorithm follows a straightforward double-loop structure, updating the current minimum and maximum while extending each sub-array. It emphasizes memory efficiency by avoiding auxiliary containers and relies on in-place variable updates.

Core Logic

The outer loop iterates over each possible starting index of a sub-array. For each start position, two variables are initialized to the element at that index, establishing the current low and high values.

size = len(nums)
for i in range(size):
    low = high = nums[i]

The inner loop expands the sub-array one element at a time, from the start index i to the end of the list. Within this loop, the algorithm updates the running minimum and maximum using the built-in min and max functions, then adds the difference to the cumulative result.

    for j in range(i, size):
        low  = min(low,  nums[j])
        high = max(high, nums[j])
        result += high - low

After all possible sub-arrays have been examined, the accumulated result is returned.

return result

Edge-Case Handling

When the input list is empty, size becomes zero, causing both loops to be skipped. The method then returns the initial value of result, which is zero, correctly representing the sum of ranges for an empty collection.

For a single-element list, the inner loop executes exactly once. Both low and high are set to that element, so the computed range high - low is zero. The method therefore returns zero, matching the expectation that a sub-array of length one has no range.

If the list contains repeated values, the incremental updates maintain the correct minimum and maximum because min and max compare the current running values with each new element, ensuring that ties are handled gracefully without affecting the range calculation.

Performance Optimizations

The algorithm achieves memory efficiency by storing only three scalar variables (low, high, and result) in addition to the loop counters. No additional arrays, stacks, or hash tables are allocated, which keeps the memory footprint minimal regardless of input size.

Incremental updates of low and high avoid recomputing the minimum and maximum from scratch for each sub-array. By carrying forward the previous state, each inner iteration performs only two constant-time comparisons, reducing the amount of work per sub-array expansion.

Using Python’s built-in min and max functions leverages highly optimized C-level implementations, providing faster execution than a manual conditional check would.

The choice of a simple nested loop structure also benefits from Python’s efficient range iterator, which generates indices on demand without constructing intermediate lists. This contributes to the overall low overhead of the solution.

Imagine a long row of numbered toy blocks lined up on a rug. This code goes through every possible combination of blocks sitting side by side in that row. It starts by picking one block and then slowly expanding a group to include the next neighbor one by one. As it adds each new block to the group, it carefully looks at all the blocks currently held to find which one has the biggest number and which one has the smallest number. It takes the biggest number and subtracts the smallest one to see the gap between them. All these differences are added together to keep a running total of the ranges found for every group. This process repeats until every group of blocks has been checked.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java				TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality