_1508. Range Sum of Sorted Subarray Sums.md

1508. Range Sum of Sorted Subarray Sums

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 04, 2024

Last updated : August 04, 2024

---

Related Topics : Array, Two Pointers, Binary Search, Sorting

Acceptance Rate : 63.18 %

---

Solutions

• m1508 v1 sort.py
• m1508 v2 heap.py

Python

m1508 v1 sort.py

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        hp = []

        for i in range(len(nums)) :
            currSum = 0
            for j in range(i, len(nums)) :
                currSum += nums[j]
                hp.append(currSum)

        hp.sort()

        return sum(hp[left-1:right]) % (10 ** 9 + 7)

m1508 v2 heap.py

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        hp = []

        for i in range(len(nums)) :
            currSum = 0
            for j in range(i, len(nums)) :
                currSum += nums[j]
                heapq.heappush(hp, currSum)
        
        output = 0
        for i in range(left - 1) :
            heapq.heappop(hp)
        for i in range(left - 1, right) :
            output += heapq.heappop(hp)

        return output % (10 ** 9 + 7)