Skip to main content

25. Sum of Subarray Ranges

hardAsked at LINE

Return the sum of (max - min) across every contiguous subarray — LINE uses this to push you past naive O(n^2) and into monotonic-stack contributions for max and min separately.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array nums. The range of a subarray is the difference between its largest and smallest element. Return the sum of all subarray ranges of nums.

Constraints

  • 1 <= nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1

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

Example 2

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

Approaches

1. Enumerate every subarray

For every (i, j), track running max and min and add the range to the total.

Time
O(n^2)
Space
O(1)
let sum=0;
for(let i=0;i<n;i++){
  let mn=nums[i], mx=nums[i];
  for(let j=i;j<n;j++){
    mn=Math.min(mn,nums[j]);
    mx=Math.max(mx,nums[j]);
    sum+=mx-mn;
  }
}
return sum;

Tradeoff:

2. Monotonic-stack contribution

Compute sum of maxes and sum of mins separately using monotonic stacks. For each element find the spans where it is the unique max (or min) and add value * leftCount * rightCount. Subtract sum of mins from sum of maxes.

Time
O(n)
Space
O(n)
function subArrayRanges(nums) {
  const contribution = (cmp) => {
    const n = nums.length, stack = [], left = Array(n), right = Array(n);
    for (let i = 0; i < n; i++) {
      while (stack.length && cmp(nums[stack[stack.length - 1]], nums[i])) stack.pop();
      left[i] = stack.length ? stack[stack.length - 1] : -1;
      stack.push(i);
    }
    stack.length = 0;
    for (let i = n - 1; i >= 0; i--) {
      while (stack.length && cmp(nums[stack[stack.length - 1]], nums[i]) || (stack.length && nums[stack[stack.length - 1]] === nums[i])) stack.pop();
      right[i] = stack.length ? stack[stack.length - 1] : n;
      stack.push(i);
    }
    let total = 0n;
    for (let i = 0; i < n; i++) total += BigInt(nums[i]) * BigInt(i - left[i]) * BigInt(right[i] - i);
    return total;
  };
  const maxes = contribution((a, b) => a <= b);
  const mins = contribution((a, b) => a >= b);
  return Number(maxes - mins);
}

Tradeoff:

LINE-specific tips

At LINE, link the contribution trick to summing per-room latency spreads when ranking which chat rooms need fan-out reshaping — chat fan-out framing wins.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Sum of Subarray Ranges and other LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →