How hard is LeetCode 1508. Range Sum of Sorted Subarray Sums?

LeetCode 1508. Range Sum of Sorted Subarray Sums is rated Medium on LeetCode.

What is the time complexity of LeetCode 1508. Range Sum of Sorted Subarray Sums?

The Python solution on this page runs in O(n^2 \times \log n).

What is the space complexity of LeetCode 1508. Range Sum of Sorted Subarray Sums?

The Python solution on this page uses O(n^2) auxiliary space.

What topics does LeetCode 1508. Range Sum of Sorted Subarray Sums cover?

LeetCode 1508. Range Sum of Sorted Subarray Sums is tagged Array, Two Pointers, Binary Search, Prefix Sum and Sorting on LeetCode.

Range Sum of Sorted Subarray Sums — LeetCode 1508 Python Solution

MediumArrayTwo PointersBinary SearchPrefix SumSorting

Problem: #1508
Pattern: Prefix Sum
Reading time: 2 min
Source: leetcode.com

The problem

You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Example

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

Python solution

Python

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        arr = []
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                arr.append(s)
        arr.sort()
        mod = 10**9 + 7
        return sum(arr[left - 1 : right]) % mod

Complexity

Measure	Complexity
Time	O(n^2 \times \log n)
Space	O(n^2) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1508. Range Sum of Sorted Subarray Sums is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1508. Range Sum of Sorted Subarray Sums?: LeetCode 1508. Range Sum of Sorted Subarray Sums is rated Medium on LeetCode.
What is the time complexity of LeetCode 1508. Range Sum of Sorted Subarray Sums?: The Python solution on this page runs in O(n^2 \times \log n).
What is the space complexity of LeetCode 1508. Range Sum of Sorted Subarray Sums?: The Python solution on this page uses O(n^2) auxiliary space.
What topics does LeetCode 1508. Range Sum of Sorted Subarray Sums cover?: LeetCode 1508. Range Sum of Sorted Subarray Sums is tagged Array, Two Pointers, Binary Search, Prefix Sum and Sorting on LeetCode.