DEV Community

Cover image for 1508. Range Sum of Sorted Subarray Sums
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1508. Range Sum of Sorted Subarray Sums

1508. Range Sum of Sorted Subarray Sums

Medium

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.length
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2

Hint:

  1. Compute all sums and save it in array.
  2. Then just go from LEFT to RIGHT index and calculate answer modulo 1e9 + 7.

Solution:

To solve this problem, we can follow these steps:

  1. Generate all possible sums of non-empty continuous subarrays.
  2. Sort the resulting array of sums.
  3. Calculate the sum of the elements from the left index to the right index (1-based).
  4. Return the result modulo 109 + 7.

Let's implement this solution in PHP: 1508. Range Sum of Sorted Subarray Sums

<?php
// Example usage
$nums = array(1, 2, 3, 4);
$n = 4;
$left = 1;
$right = 5;

echo rangeSum($nums, $n, $left, $right); // Output: 13

$left = 3;
$right = 4;
echo rangeSum($nums, $n, $left, $right); // Output: 6

$left = 1;
$right = 10;
echo rangeSum($nums, $n, $left, $right); // Output: 50

?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Generating Subarray Sums:

    • Iterate through each starting index i of the subarray.
    • For each starting index i, compute the sum of subarrays ending at index j (where j >= i).
    • Append each computed subarray sum to the $sums array.
  2. Sorting the Sums:

    • Use PHP's sort() function to sort the $sums array in non-decreasing order.
  3. Summing the Required Range:

    • Iterate from the left-1 index to the right-1 index (since the problem uses 1-based indexing).
    • Accumulate the sum of the elements in this range, taking care to use modulo 109 + 7 to avoid overflow.

This solution efficiently generates all subarray sums, sorts them, and computes the required range sum as specified.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI tool

Transforming Interviews into Publishable Stories with AssemblyAI

Insightview is a modern web application that streamlines the interview workflow for journalists. By leveraging AssemblyAI's LeMUR and Universal-2 technology, it transforms raw interview recordings into structured, actionable content, dramatically reducing the time from recording to publication.

Key Features:
🎥 Audio/video file upload with real-time preview
🗣️ Advanced transcription with speaker identification
⭐ Automatic highlight extraction of key moments
✍️ AI-powered article draft generation
📤 Export interview's subtitles in VTT format

Read full post

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay