Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1712.html
1712. Ways to Split Array Into Three Subarrays
Level
Medium
Description
A split of an integer array is good if:
- The array is split into three non-empty contiguous subarrays - named
left,mid,rightrespectively from left to right. - The sum of the elements in
leftis less than or equal to the sum of the elements inmid, and the sum of the elements inmidis less than or equal to the sum of the elements inright.
Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10^9 + 7.
Example 1:
Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].
Example 2:
Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
Example 3:
Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.
Constraints:
3 <= nums.length <= 10^50 <= nums[i] <= 10^4
Solution
Calculate the prefix sum array of nums and determine the maximum possible sum of the elements in left.
For each possible sum of elements in left, use binary search to determine the maximum end index and the minimum end index of mid, which are maxMidIndex and minMidIndex, and add maxMidIndex - minMidIndex + 1 to the number of ways.
Finally, return the number of ways.
-
class Solution { public int waysToSplit(int[] nums) { final int MODULO = 1000000007; int ways = 0; int length = nums.length; int[] prefixSums = new int[length]; prefixSums[0] = nums[0]; for (int i = 1; i < length; i++) prefixSums[i] = prefixSums[i - 1] + nums[i]; int sum = prefixSums[length - 1]; int maxLeft = sum / 3; int maxLeftIndex = binarySearchMax(prefixSums, maxLeft); for (int i = 0; i <= maxLeftIndex; i++) { int leftSum = prefixSums[i]; int minMid = leftSum * 2, maxMid = (sum + leftSum) / 2; int minMidIndex = binarySearchMin(prefixSums, minMid, i + 1); int maxMidIndex = binarySearchMax(prefixSums, maxMid); if (maxMidIndex >= minMidIndex) { int curWays = maxMidIndex - minMidIndex + 1; ways = (ways + curWays) % MODULO; } } return ways; } public int rangeSum(int[] prefixSums, int start, int end) { if (start == 0) return prefixSums[end]; else return prefixSums[end] - prefixSums[start - 1]; } public int binarySearchMax(int[] prefixSums, int upper) { if (prefixSums[0] > upper) return -1; int low = 0, high = prefixSums.length - 2; while (low < high) { int mid = (high - low + 1) / 2 + low; int cur = prefixSums[mid]; if (cur > upper) high = mid - 1; else low = mid; } return high; } public int binarySearchMin(int[] prefixSums, int lower, int startIndex) { if (prefixSums[prefixSums.length - 1] < lower) return prefixSums.length; int low = startIndex, high = prefixSums.length - 1; while (low < high) { int mid = (high - low) / 2 + low; int cur = prefixSums[mid]; if (cur < lower) low = mid + 1; else high = mid; } return low; } } ############ class Solution { private static final int MOD = (int) 1e9 + 7; public int waysToSplit(int[] nums) { int n = nums.length; int[] s = new int[n]; s[0] = nums[0]; for (int i = 1; i < n; ++i) { s[i] = s[i - 1] + nums[i]; } int ans = 0; for (int i = 0; i < n - 2; ++i) { int j = search(s, s[i] << 1, i + 1, n - 1); int k = search(s, ((s[n - 1] + s[i]) >> 1) + 1, j, n - 1); ans = (ans + k - j) % MOD; } return ans; } private int search(int[] s, int x, int left, int right) { while (left < right) { int mid = (left + right) >> 1; if (s[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } } -
// OJ: https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/ // Time: O(NlogN) // Space: O(1) if we are allowed to change the input array; otherwise O(N) class Solution { public: int waysToSplit(vector<int>& A) { long N = A.size(), mod = 1e9 + 7, ans = 0; partial_sum(begin(A), end(A), begin(A)); for (int i = 0; i < N - 2; ++i) { int j = lower_bound(begin(A) + i + 1, end(A) - 1, A[i] * 2) - begin(A); int k = upper_bound(begin(A) + j, end(A) - 1, A[i] + (A.back() - A[i]) / 2) - begin(A); ans = (ans + k - j) % mod; } return ans; } }; -
class Solution: def waysToSplit(self, nums: List[int]) -> int: mod = 10**9 + 7 s = list(accumulate(nums)) ans, n = 0, len(nums) for i in range(n - 2): j = bisect_left(s, s[i] << 1, i + 1, n - 1) k = bisect_right(s, (s[-1] + s[i]) >> 1, j, n - 1) ans += k - j return ans % mod ############ # 1712. Ways to Split Array Into Three Subarrays # https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/ class Solution: def waysToSplit(self, nums: List[int]): prefix = [0] for num in nums: prefix.append(prefix[-1] + num) M = 10 ** 9 + 7 ans = 0 for i in range(1, len(nums)): j = bisect_left(prefix, 2*prefix[i]) k = bisect_right(prefix, (prefix[i] + prefix[-1])//2) ans += max(0, min(len(nums), k) - max(i+1, j)) return ans % M def helper(self, prefix, leftSum, i, searchLeft): n = len(prefix) left, right = i, n - 2 res = -1 while left <= right: mid = left + (right-left) // 2 midSum = prefix[mid] - prefix[i - 1] rightSum = prefix[-1] - prefix[mid] if leftSum <= midSum <= rightSum: res = mid if searchLeft: right = mid - 1 else: left = mid + 1 elif leftSum > midSum: left = mid + 1 else: right = mid - 1 return res def waysToSplit(self, nums: List[int]): M = 10 ** 9 + 7 n = len(nums) prefix = [nums[0]] for num in nums[1:]: prefix.append(prefix[-1] + num) res = 0 for i in range(1, n-1): leftSum = prefix[i-1] mid = self.helper(prefix, leftSum, i, True) right = self.helper(prefix, leftSum, i, False) if mid == -1 or right == - 1: continue res += (right - mid + 1) res %= M return res % M -
func waysToSplit(nums []int) (ans int) { const mod int = 1e9 + 7 n := len(nums) s := make([]int, n) s[0] = nums[0] for i := 1; i < n; i++ { s[i] = s[i-1] + nums[i] } for i := 0; i < n-2; i++ { j := sort.Search(n-1, func(h int) bool { return h > i && s[h] >= (s[i]<<1) }) k := sort.Search(n-1, func(h int) bool { return h >= j && s[h] > (s[n-1]+s[i])>>1 }) ans = (ans + k - j) % mod } return } -
/** * @param {number[]} nums * @return {number} */ var waysToSplit = function (nums) { const mod = 1e9 + 7; const n = nums.length; const s = new Array(n).fill(nums[0]); for (let i = 1; i < n; ++i) { s[i] = s[i - 1] + nums[i]; } function search(s, x, left, right) { while (left < right) { const mid = (left + right) >> 1; if (s[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } let ans = 0; for (let i = 0; i < n - 2; ++i) { const j = search(s, s[i] << 1, i + 1, n - 1); const k = search(s, ((s[n - 1] + s[i]) >> 1) + 1, j, n - 1); ans = (ans + k - j) % mod; } return ans; };