Tap here to switch tabs

Problem

Ask

Submissions

Solution

Grokking the Coding Interview Patterns

Solution: Range Sum of Sorted Subarray Sums

Statement▼

You are given an integer array nums containing $n$ positive integers along with left and right. Calculate the sum of its elements for every non-empty continuous subarray of nums. Collect these sums into a new array and sort it in nondecreasing order. This will result in a new array of size $n \times (n + 1) /2$ .

Your task is to return the sum of the elements in this sorted array from the index left to right (inclusive with 1-based indexing).

Note: As the result can be large, return the sum modulo $10^9 + 7$ .

Constraints:

$n =$ nums.length
$1 \leq$ nums.length $\leq 1000$
$1 \leq$ nums[i] ...

⋮

Tap here to switch tabs

Problem

Ask

Submissions

Solution

Grokking the Coding Interview Patterns

Solution: Range Sum of Sorted Subarray Sums

Statement▼

You are given an integer array nums containing $n$ positive integers along with left and right. Calculate the sum of its elements for every non-empty continuous subarray of nums. Collect these sums into a new array and sort it in nondecreasing order. This will result in a new array of size $n \times (n + 1) /2$ .

Your task is to return the sum of the elements in this sorted array from the index left to right (inclusive with 1-based indexing).

Note: As the result can be large, return the sum modulo $10^9 + 7$ .

Constraints:

$n =$ nums.length
$1 \leq$ nums.length $\leq 1000$
$1 \leq$ nums[i] ...