Sum of Subarray Ranges

Medium
397.

Sum of Subarray Ranges

Sum of Subarray Ranges is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Google interviews.

The range of a subarray is the difference between its largest and smallest element.

Given an integer array nums, return the sum of the ranges of all its contiguous non-empty subarrays.

Example 1

Input
nums = [1,2,3]
Output
4
Explanation
The ranges are 0,0,0,1,1,2.

Example 2

Input
nums = [1,3,3]
Output
4

Example 3

Input
nums = [4,-2,-3,4,1]
Output
59

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000

Follow-up: The O(n²) sweep is straightforward. Can you do it in O(n) with two monotonic stacks — sum of maximums minus sum of minimums?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var subArrayRanges = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of Subarray Ranges — Solution in Python, Java & C++

Sum of Subarray Ranges solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sum of Subarray Ranges is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Stack, Monotonic Stack
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The range of a subarray is the difference between its largest and smallest element.

Given an integer array nums, return the sum of the ranges of all its contiguous non-empty subarrays.

Example 1

Input: nums = [1,2,3]
Output: 4
Explanation: The ranges are 0,0,0,1,1,2.

Example 2

Input: nums = [1,3,3]
Output: 4

Example 3

Input: nums = [4,-2,-3,4,1]
Output: 59

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000

Follow-up: The O(n²) sweep is straightforward. Can you do it in O(n) with two monotonic stacks — sum of maximums minus sum of minimums?

Hints for Sum of Subarray Ranges

  1. Hint 1

    Fix the left end and extend right, keeping a running minimum and maximum.

  2. Hint 2

    Each extension contributes max - min in constant time, giving O(n²).

  3. Hint 3

    For O(n), note the answer is the sum of subarray maximums minus the sum of subarray minimums, each computable with a monotonic stack.

How to solve Sum of Subarray Ranges

Fix the left end and extend right, keeping a running min and max; each extension adds max - min in O(1).

Approach

  1. For each i, set lo = hi = nums[i].
  2. For each j >= i, update lo, hi and add hi - lo.

Why it works

Every subarray is visited exactly once, and its range is maintained incrementally as it grows.

Complexity

  • Time — O(n²)
  • Space — O(1)

Pitfalls

  • For O(n), compute Σ subarray maximums minus Σ subarray minimums with two monotonic-stack passes.

Reference solution

Python

def subArrayRanges(nums) -> int:
    total = 0
    n = len(nums)
    for i in range(n):
        lo = hi = nums[i]
        for j in range(i, n):
            lo = min(lo, nums[j])
            hi = max(hi, nums[j])
            total += hi - lo
    return total

Java

public static int subArrayRanges(int[] nums) {
    int total = 0;
    for (int i = 0; i < nums.length; i++) {
        int lo = nums[i], hi = nums[i];
        for (int j = i; j < nums.length; j++) {
            lo = Math.min(lo, nums[j]);
            hi = Math.max(hi, nums[j]);
            total += hi - lo;
        }
    }
    return total;
}

C++

int subArrayRanges(vector<int>& nums) {
    int total = 0;
    int n = (int) nums.size();
    for (int i = 0; i < n; i++) {
        int lo = nums[i], hi = nums[i];
        for (int j = i; j < n; j++) {
            lo = min(lo, nums[j]);
            hi = max(hi, nums[j]);
            total += hi - lo;
        }
    }
    return total;
}

JavaScript

var subArrayRanges = function(nums) {
    let total = 0;
    for (let i = 0; i < nums.length; i++) {
        let lo = nums[i], hi = nums[i];
        for (let j = i; j < nums.length; j++) {
            if (nums[j] < lo) lo = nums[j];
            if (nums[j] > hi) hi = nums[j];
            total += hi - lo;
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure