NeetCode #546LC-1508MediumHeap / Priority Queue
← Back to All Problems#546 · #1508 · Range Sum of Sorted Subarray Sums(子数组和排序后的区间和)
📌 Problem Statement & Constraints
Given an array
nums of n positive integers and integers left and right, consider all n(n+1)/2 subarray sums, sort them ascending, and return the sum of the elements from index left to right (1-indexed), modulo 10^9 + 7. Constraints: 1 <= n <= 1000, 1 <= nums[i] <= 100, 1 <= left <= right <= n(n+1)/2.💡 Core Algorithmic Approaches
- Generate all
O(n^2)subarray sums and sort them. - Then sum the requested slice and take the modulo.
- With
n <= 1000there are about 500k sums, so sorting is comfortably fast. - A binary-search-on-the-answer approach would be needed for much larger
n.
💻 Benchmark Python3 Implementation
class Solution:
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
MOD = 10 ** 9 + 7
sums = []
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j] # running sum of nums[i..j]
sums.append(s)
sums.sort()
return sum(sums[left - 1:right]) % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 log n): generating O(n^2) sums and sorting them.
💾 Space Complexity
O(n^2) for the sums array.
⚠️ Interview Pitfalls & Follow-ups
- Using 0-indexed
left/right: the problem is 1-indexed, so the slice is[left - 1 : right]. - Forgetting the modulo: the answer can be very large.
- Recomputing each subarray sum from scratch: the running sum keeps generation at O(n^2).
- Sorting a set instead of a list: duplicate sums are distinct subarrays and must all be counted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.