DSA interview question

Sum of Subarray Ranges

Medium · Data structures · Topics: stack, monotonic stack

The problem

A volatility report sums, over every contiguous window of a price series, the window's range (max − min). With O(n²) windows, that's too slow for large inputs if done naively. The sum of ranges splits into (sum of window maximums) − (sum of window minimums), and each part has the same contribution trick as "sum of subarray minimums": count how many windows each element dominates using previous and next boundaries from monotonic stacks. The maximum part is just the minimum part applied to the negated array.

Example: [1, 2, 3] → 4.

Function signature

long long subArrayRanges(const vector<int>& nums);

Test cases

Input	Output	Explanation
`[1, 2, 3]`	`4`	Ranges 0, 0, 0, 1, 1, 2
`[1, 3, 3]`	`4`	Ranges 0, 0, 0, 2, 0, 2
`[4, -2, -3, 4, 1]`	`59`
`[5]`	`0`
`[2, 2]`	`0`

(Confirm: every non-empty contiguous subarray counts once; values may be negative; the answer fits in 64 bits.)

How interviewers phrase it

"Return the sum of all subarray ranges, where a range is the difference between the largest and smallest element" (LeetCode 2104), "in O(n)".

Clarifying questions to ask

Contiguous subarrays? (Yes.)
How large is n? (1000 allows O(n²); the follow-up asks for O(n).)
Can values be negative? (Yes.)

Follow-ups to expect

"Simple O(n²) approach?"
"How do you get O(n)?"
"How do you reuse one function for both?"
"How are ties handled?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview