Skip to main content

1508. Range Sum of Sorted Subarray Sums

medium

Compute every subarray sum, sort them, then return the sum of entries from position left to right. The O(n^2) approach is straightforward — the O(n log^2 n) trick is interview gold.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays and then sorted them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers. Return the sum of the numbers from index left to index right (indices are 1-indexed), modulo 10^9 + 7.

Constraints

  • n == nums.length
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2

Examples

Example 1

Input
nums = [1,2,3,4], n = 4, left = 1, right = 5
Output
13

Explanation: Subarray sums sorted: [1,2,3,3,4,5,6,7,9,10]. Sum of indices 1..5 is 1+2+3+3+4 = 13.

Example 2

Input
nums = [1,2,3,4], n = 4, left = 3, right = 4
Output
6

Explanation: Sum of indices 3..4 is 3+3 = 6.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force: enumerate all O(n^2) subarray sums, sort, prefix-sum, answer the range. O(n^2 log n) — fine for n=1000.

Hint 2

Faster path: binary-search the answer. Find prefix(k) = sum of the k smallest subarray sums.

Hint 3

Define f(x) = count of subarray sums <= x. f is monotonic; binary-search x for any target count k.

Hint 4

Compute prefix(k) with a sliding-window helper that also tracks the partial sum. Answer = prefix(right) - prefix(left - 1).

Solution approach

Reveal approach

Two paths. Path A (accepted, brute force): generate all n*(n+1)/2 subarray sums via prefix sums, sort, take the slice [left-1, right-1], sum modulo 10^9 + 7. O(n^2 log n) time and O(n^2) space — fits the constraints. Path B (optimal interview answer): binary-search on the answer. Define count(x) = number of subarray sums <= x, computable in O(n) via a sliding window because nums has positive values. Binary-search the smallest x such that count(x) >= k; call it x_k. Then prefix(k) = (sum of all subarray sums <= x_k) - (count(x_k) - k) * x_k, where the sum-of-all is also computed in the same sliding-window pass. Final answer: (prefix(right) - prefix(left - 1)) mod (10^9 + 7). O(n log(sum) log(sum)) time, O(n) space. The trick is realizing the count(x) predicate is monotonic in x, which unlocks the binary-search-on-answer skeleton.

Complexity

Time
O(n^2 log n) brute / O(n log^2 S) optimal where S = total sum
Space
O(n^2) brute / O(n) optimal

Related patterns

  • binary-search
  • binary-search-on-answer
  • sliding-window
  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More Binary Search practice problems

See all Binary Search problems →