Range Sum of Sorted Subarray Sums

Range Sum of Sorted Subarray Sums

What is this problem about?

The Range Sum of Sorted Subarray Sums problem asks you to: find all possible subarray sums of an array, sort them, and return the sum of elements from index left to right (1-indexed) in this sorted list, modulo 10^9+7. This coding problem generates all subarray sums, sorts them, and computes a range sum. The array, sorting, two pointers, binary search, and prefix sum interview pattern is demonstrated.

Why is this asked in interviews?

Amazon, Google, and Bloomberg ask this to test the candidate's ability to generate all O(n²) subarray sums efficiently and apply binary search or two-pointer techniques for the sorted order without materializing all sums.

Algorithmic pattern used

Generate all subarray sums + sort + prefix sum. For an array of n elements, there are n*(n+1)/2 subarray sums. Naive: compute all, sort, take prefix sum for [left, right]. Efficient: use binary search to find the count of sums ≤ a value (two-pointer sweep), then compute the exact values.

Example explanation

nums=[1,2,3,4], left=1, right=5. All subarray sums: [1,2,3,4,3,5,6,7,9,10] — sorted: [1,2,3,3,4,5,6,7,9,10]. Sum of positions 1-5: 1+2+3+3+4 = 13.

Common mistakes candidates make

• Not applying modulo during summation (overflow).
• Off-by-one: 1-indexed vs 0-indexed in the sorted list.
• O(n² log n) naive approach acceptable for small n; binary search approach for larger.
• Generating non-contiguous subsets instead of subarrays.

Interview preparation tip

Range Sum of Sorted Subarray Sums tests your ability to generate subarray sums systematically. The naive O(n² log n) approach works for small n. The optimized approach uses binary search: "how many subarray sums are ≤ x?" with a two-pointer O(n) check. Practice similar "sort all O(n²) quantities and answer range queries" problems — they test both generation efficiency and range query skills.