Range sum of sorted subarray sums

Array Two Pointers Binary Search Sorting Prefix Sum

63.1% acceptance

Feb 25, 2026

1601

268

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn range_sum(nums: Vec<i32>, _n: i32, left: i32, right: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    let mut sums = Vec::with_capacity(n * (n + 1) / 2);
    for i in 0..n {
      let mut s = 0i64;
      for j in i..n {
        s += nums[j] as i64;
        sums.push(s);
      }
    }
    sums.sort();
    let ans: i64 = sums[(left as usize - 1)..(right as usize)]
      .iter().map(|&x| x % MOD).sum::<i64>() % MOD;
    ans as i32
  }
}