{"id":7897,"date":"2021-01-03T00:44:40","date_gmt":"2021-01-03T08:44:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7897"},"modified":"2021-01-03T00:57:41","modified_gmt":"2021-01-03T08:57:41","slug":"leetcode-1712-ways-to-split-array-into-three-subarrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1712-ways-to-split-array-into-three-subarrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1712. Ways to Split Array Into Three Subarrays"},"content":{"rendered":"\n<p>A split of an integer array is&nbsp;<strong>good<\/strong>&nbsp;if:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The array is split into three&nbsp;<strong>non-empty<\/strong>&nbsp;contiguous subarrays &#8211; named&nbsp;<code>left<\/code>,&nbsp;<code>mid<\/code>,&nbsp;<code>right<\/code>&nbsp;respectively from left to right.<\/li><li>The sum of the elements in&nbsp;<code>left<\/code>&nbsp;is less than or equal to the sum of the elements in&nbsp;<code>mid<\/code>, and the sum of the elements in&nbsp;<code>mid<\/code>&nbsp;is less than or equal to the sum of the elements in&nbsp;<code>right<\/code>.<\/li><\/ul>\n\n\n\n<p>Given&nbsp;<code>nums<\/code>, an array of&nbsp;<strong>non-negative<\/strong>&nbsp;integers, return&nbsp;<em>the number of&nbsp;<strong>good<\/strong>&nbsp;ways to split<\/em>&nbsp;<code>nums<\/code>. As the number may be too large, return it&nbsp;<strong>modulo<\/strong>&nbsp;<code>10<sup>9&nbsp;<\/sup>+ 7<\/code>.<\/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,1,1]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The only good way to split nums is [1] [1] [1].<\/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,2,2,5,0]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> There are three good ways of splitting nums:\n[1] [2] [2,2,5,0]\n[1] [2,2] [2,5,0]\n[1,2] [2,2] [5,0]\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 = [3,2,1]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> There is no good way to split nums.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>3 &lt;= nums.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= nums[i] &lt;= 10<sup>4<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Prefix Sum + Binary Search<\/strong><\/h2>\n\n\n\n<p>We split the array into [0 &#8230; i] [i + 1&#8230; j] [j + 1 &#8230; n &#8211; 1]<br>we can use binary search to find the min and max of j for each i.<br>s.t.  sum(0 ~ i) &lt;= sums(i + 1 ~j) &lt;= sums(j + 1 ~ n &#8211; 1)<br>min is lower_bound(2 * sums(0 ~ i))<br>max is upper_bound(sums(0 ~ i) + (total &#8211; sums(0 ~ i)) \/ 2)<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(1)<\/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 waysToSplit(vector<int>& nums) {\n    constexpr int kMod = 1e9 + 7;\n    const int n = nums.size();    \n    for (int i = 1; i < n; ++i) \n      nums[i] += nums[i - 1];\n    const int total = nums.back();\n    long ans = 0;  \n    \/\/ [0 .. i] [i + 1 ... j] [j + 1 ... n - 1]\n    for (int i = 0, left = 0; i < n; ++i) {      \n      auto it1 = lower_bound(begin(nums) + i + 1, end(nums), 2 * nums[i]);\n      auto it2 = upper_bound(begin(nums), end(nums) - 1, nums[i] + (total - nums[i]) \/ 2);\n      if (it2 <= it1) continue;\n      ans += it2 - it1;\n    }    \n    return ans % kMod;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Prefix Sum + Two Pointers<\/strong><\/h2>\n\n\n\n<p>The right end of the middle array is in range [j, k - 1] and there are k - j choices.<br>Time complexity: O(n)<br>Space complexity: O(1)<\/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 waysToSplit(vector<int>& nums) {\n    constexpr int kMod = 1e9 + 7;\n    const int n = nums.size();    \n    for (int i = 1; i < n; ++i) \n      nums[i] += nums[i - 1];\n    const int total = nums.back();\n    long ans = 0;    \n    for (int i = 0, j = 0, k = 0; i < n; ++i) {      \n      j = max(j, i + 1);\n      while (j < n - 1 &#038;&#038; nums[j] < 2 * nums[i]) ++j;\n      k = max(k, j);\n      while (k < n - 1 &#038;&#038; 2 * nums[k] <= nums[i] + total) ++k;\n      ans += (k - j);\n    }    \n    return ans % kMod;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A split of an integer array is&nbsp;good&nbsp;if: The array is split into three&nbsp;non-empty&nbsp;contiguous subarrays &#8211; named&nbsp;left,&nbsp;mid,&nbsp;right&nbsp;respectively from left to right. The sum of the elements&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,177,683,175],"class_list":["post-7897","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","tag-split-array","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7897","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=7897"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7897\/revisions"}],"predecessor-version":[{"id":7900,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7897\/revisions\/7900"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7897"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7897"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7897"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}