Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 109 + 7.
Example 1:
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.
Example 2:
Input: nums = [1,2,3,4], n = 4, left = 3, right = 4 Output: 6 Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.
Example 3:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 10 Output: 50
Constraints:
n == nums.length1 <= nums.length <= 10001 <= nums[i] <= 1001 <= left <= right <= n * (n + 1) / 2Problem summary: 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. Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Two Pointers · Binary Search
[1,2,3,4] 4 1 5
[1,2,3,4] 4 3 4
[1,2,3,4] 4 1 10
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1508: Range Sum of Sorted Subarray Sums
class Solution {
public int rangeSum(int[] nums, int n, int left, int right) {
int[] arr = new int[n * (n + 1) / 2];
for (int i = 0, k = 0; i < n; ++i) {
int s = 0;
for (int j = i; j < n; ++j) {
s += nums[j];
arr[k++] = s;
}
}
Arrays.sort(arr);
int ans = 0;
final int mod = (int) 1e9 + 7;
for (int i = left - 1; i < right; ++i) {
ans = (ans + arr[i]) % mod;
}
return ans;
}
}
// Accepted solution for LeetCode #1508: Range Sum of Sorted Subarray Sums
func rangeSum(nums []int, n int, left int, right int) (ans int) {
var arr []int
for i := 0; i < n; i++ {
s := 0
for j := i; j < n; j++ {
s += nums[j]
arr = append(arr, s)
}
}
sort.Ints(arr)
const mod int = 1e9 + 7
for _, x := range arr[left-1 : right] {
ans = (ans + x) % mod
}
return
}
# Accepted solution for LeetCode #1508: Range Sum of Sorted Subarray Sums
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
// Accepted solution for LeetCode #1508: Range Sum of Sorted Subarray Sums
struct Solution;
const MOD: i64 = 1_000_000_007;
impl Solution {
fn range_sum(nums: Vec<i32>, n: i32, left: i32, right: i32) -> i32 {
let mut sums = vec![];
let n = n as usize;
for i in 0..n {
let k = sums.len();
for j in 0..i {
sums.push(sums[k - 1 - j] + nums[i]);
}
sums.push(nums[i]);
}
sums.sort_unstable();
let mut res = 0;
let start = left as usize - 1;
let end = right as usize;
for i in start..end {
res += sums[i] as i64;
res %= MOD;
}
res as i32
}
}
#[test]
fn test() {
let nums = vec![1, 2, 3, 4];
let n = 4;
let left = 1;
let right = 5;
let res = 13;
assert_eq!(Solution::range_sum(nums, n, left, right), res);
let nums = vec![1, 2, 3, 4];
let n = 4;
let left = 3;
let right = 4;
let res = 6;
assert_eq!(Solution::range_sum(nums, n, left, right), res);
let nums = vec![1, 2, 3, 4];
let n = 4;
let left = 1;
let right = 10;
let res = 50;
assert_eq!(Solution::range_sum(nums, n, left, right), res);
}
// Accepted solution for LeetCode #1508: Range Sum of Sorted Subarray Sums
function rangeSum(nums: number[], n: number, left: number, right: number): number {
let arr = Array((n * (n + 1)) / 2).fill(0);
const mod = 10 ** 9 + 7;
for (let i = 0, s = 0, k = 0; i < n; i++, s = 0) {
for (let j = i; j < n; j++, k++) {
s += nums[j];
arr[k] = s;
}
}
arr = arr.sort((a, b) => a - b).slice(left - 1, right);
return arr.reduce((acc, cur) => (acc + cur) % mod, 0);
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.