#1508 - Range Sum of Sorted Subarray Sums

Medium • View on LeetCode • View on GitHub

Array Sorting Binary Search Two Pointers Prefix Sum

Problem Description

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

/**
 * @param {number[]} nums
 * @param {number} n
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var rangeSum = function(nums, n, left, right) {
  const MOD = 1e9 + 7;
  const sums = [];

  for (let start = 0; start < n; start++) {
    let currentSum = 0;
    for (let end = start; end < n; end++) {
      currentSum += nums[end];
      sums.push(currentSum);
    }
  }

  sums.sort((a, b) => a - b);

  let result = 0;
  for (let i = left - 1; i < right; i++) {
    result = (result + sums[i]) % MOD;
  }

  return result;
};