⚡Flashcard Drill➔
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

  1. Generate all O(n^2) subarray sums and sort them.
  2. Then sum the requested slice and take the modulo.
  3. With n <= 1000 there are about 500k sums, so sorting is comfortably fast.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems