{"id":7071,"date":"2020-07-11T21:22:08","date_gmt":"2020-07-12T04:22:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7071"},"modified":"2020-07-12T17:26:04","modified_gmt":"2020-07-13T00:26:04","slug":"leetcode-1508-range-sum-of-sorted-subarray-sums","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/queue\/leetcode-1508-range-sum-of-sorted-subarray-sums\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1508. Range Sum of Sorted Subarray Sums"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1508. Range Sum of Sorted Subarray Sums - \u5237\u9898\u627e\u5de5\u4f5c EP343\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/6UJEMVmMJDw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given the array&nbsp;<code>nums<\/code>&nbsp;consisting of&nbsp;<code>n<\/code>&nbsp;positive integers. You computed the sum of all non-empty continous subarrays from&nbsp;the array and then sort them in non-decreasing order, creating a new array of&nbsp;<code>n * (n + 1) \/ 2<\/code>&nbsp;numbers.<\/p>\n\n\n\n<p><em>Return the sum of the numbers from index&nbsp;<\/em><code>left<\/code><em>&nbsp;to index&nbsp;<\/em><code>right<\/code>&nbsp;(<strong>indexed from 1<\/strong>)<em>, inclusive, in the&nbsp;new array.&nbsp;<\/em>Since the answer can be a huge number return it modulo 10^9 + 7.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,3,4], n = 4, left = 1, right = 5\n<strong>Output:<\/strong> 13 \n<strong>Explanation:<\/strong> 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. \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,3,4], n = 4, left = 3, right = 4\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> 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.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,3,4], n = 4, left = 1, right = 10\n<strong>Output:<\/strong> 50\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 10^3<\/code><\/li><li><code>nums.length == n<\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 100<\/code><\/li><li><code>1 &lt;= left &lt;= right&nbsp;&lt;= n * (n + 1) \/ 2<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-1.png\" alt=\"\" class=\"wp-image-7093\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Find sums of all the subarrays and sort the values.<\/p>\n\n\n\n<p>Time complexity: O(n^2logn)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int rangeSum(vector<int>& nums, int n, int left, int right) {\n    constexpr int kMod = 1e9 + 7;\n    vector<int> sums;\n    for (int i = 0; i < n; ++i)      \n      for (int j = i, sum = 0; j < n; ++j)\n        sums.push_back(sum += nums[j]);\n    sort(begin(sums), end(sums));\n    return accumulate(begin(sums) + left - 1, begin(sums) + right, 0LL) % kMod;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\n\/\/ Author: Huahua\nclass Solution {\n  public int rangeSum(int[] nums, int n, int left, int right) {\n    final int kMod = (int)(1e9 + 7);\n    int[] sums = new int[n * (n + 1) \/ 2];\n    int idx = 0;\n    for (int i = 0; i < n; ++i)\n      for (int j = i, sum = 0; j < n; ++j, ++idx)\n        sums[idx] = sum += nums[j];\n    Arrays.sort(sums);\n    int ans = 0;\n    for (int i = left; i <= right; ++i)\n      ans = (ans + sums[i - 1]) % kMod;\n    return ans;\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n    sums = []\n    for i in range(n):\n      s = 0\n      for j in range(i, n):\n        s += nums[j]\n        sums.append(s)\n    sums.sort()\n    return sum(sums[left - 1:right])\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Priority Queue<\/strong> <strong>\/ Min Heap<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-2.png\" alt=\"\" class=\"wp-image-7094\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>For each subarray, start with one element e.g nums[i], put them into a priority queue (min heap). Each time, we have the smallest subarray sum, and extend that subarray and put the new sum back into priority queue. Thought it has the same time complexity as the brute force one in worst case, but space complexity can be reduce to O(n).<\/p>\n\n\n\n<p>Time complexity: O(n^2logn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nstruct Entry {\n  int sum;\n  int i;\n  bool operator<(const Entry&#038; e) const { return sum > e.sum; }\n};\n\nclass Solution {\npublic:\n  int rangeSum(vector<int>& nums, int n, int left, int right) {\n    constexpr int kMod = 1e9 + 7;\n    priority_queue<Entry> q; \/\/ Sort by e.sum in descending order.\n    for (int i = 0; i < n; ++i)\n      q.push({nums[i], i});\n    long ans = 0;\n    for (int j = 1; j <= right; ++j) {\n      const auto e = std::move(q.top()); q.pop();\n      if (j >= left) ans += e.sum;\n      if (e.i + 1 < n) q.push({e.sum + nums[e.i + 1], e.i + 1});\n    }\n    return ans % kMod;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nimport java.util.AbstractMap;\nclass Solution {\n  public int rangeSum(int[] nums, int n, int left, int right) {\n    final int kMod = (int)(1e9 + 7);\n    var q = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> a.getKey() - b.getKey());\n    for (int i = 0; i < n; ++i)\n      q.offer(new AbstractMap.SimpleEntry<>(nums[i], i));\n    \n    int ans = 0;\n    for (int k = 1; k <= right; ++k) {      \n      var e = q.poll();\n      int sum = e.getKey();\n      int i = e.getValue();\n      if (k >= left) \n        ans = (ans + sum) % kMod;\n      if (i + 1 < n) \n        q.offer(new AbstractMap.SimpleEntry<>(sum + nums[i + 1], i + 1));\n    }\n    return ans;\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n# Author: Huahua\nclass Solution:\n  def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n    q = [(num, i) for i, num in enumerate(nums)]\n    heapq.heapify(q)\n    ans = 0\n    for k in range(1, right + 1):\n      s, i = heapq.heappop(q)\n      if k >= left:\n        ans += s\n      if i + 1 < n:\n        heapq.heappush(q, (s + nums[i + 1], i + 1))\n    return ans % int(1e9 + 7)\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 3: Binary Search + Sliding Window<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-3.png\" alt=\"\" class=\"wp-image-7095\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-4.png\" alt=\"\" class=\"wp-image-7096\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1508-ep343-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Use binary search to find S s.t. that there are at least k subarrys have sum &lt;= S.<\/p>\n\n\n\n<p>Given S, we can use sliding window to count how many subarrays have sum &lt;= S and their total sum.<\/p>\n\n\n\n<p>ans = sums_of_first(right) - sums_of_first(left - 1).<\/p>\n\n\n\n<p>Time complexity: O(n * log(sum(nums))<br>Space complexity: O(n) <\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int rangeSum(vector<int>& nums, int n, int left, int right) {\n    constexpr int kMod = 1e9 + 7;    \n    \/\/ Returns number of subarrays that have \n    \/\/ sum <= target and their total sum.\n    auto countAndSum = [&#038;](int target) -> pair<int, long> {\n      int count = 0;\n      long cur = 0;\n      long sum = 0;\n      long total_sum = 0;\n      for (long j = 0, i = 0; j < n; ++j) {\n        cur += nums[j];\n        sum += nums[j] * (j - i + 1);\n        while (cur > target) {          \n          sum -= cur;\n          cur -= nums[i++];\n        }        \n        count += j - i + 1;\n        total_sum += sum;\n      }\n      return {count, total_sum};\n    };\n    \n    \/\/ Returns the total sums of smallest k subarrays.\n    \/\/ Use binary search to find the smallest sum l s.t. \n    \/\/ there are at least k of subarrays have sums <= l.\n    const int min_sum = *min_element(begin(nums), end(nums));\n    const int max_sum = accumulate(begin(nums), end(nums), 0) + 1;\n    auto sumOfFirstK = [&#038;](int k) -> long {\n      int l = min_sum;\n      int r = max_sum;\n      while (l < r) {\n        int mid = l + (r - l) \/ 2;\n        if (countAndSum(mid).first >= k)\n          r = mid;\n        else\n          l = mid + 1;\n      }      \n      const auto [count, sum] = countAndSum(l);\n      \/\/ There can be more subarrays have the same sum of l.      \n      return sum - l * (count - k);\n    };\n    \n    return (sumOfFirstK(right) - sumOfFirstK(left - 1)) % kMod;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given the array&nbsp;nums&nbsp;consisting of&nbsp;n&nbsp;positive integers. You computed the sum of all non-empty continous subarrays from&nbsp;the array and then sort them in non-decreasing order, creating a&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[429],"tags":[52,177,200,215,23,41],"class_list":["post-7071","post","type-post","status-publish","format-standard","hentry","category-queue","tag-binary-search","tag-medium","tag-prefix-sum","tag-sliding-window","tag-sort","tag-subarray","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7071","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7071"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7071\/revisions"}],"predecessor-version":[{"id":7099,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7071\/revisions\/7099"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7071"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7071"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7071"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}