LeetCode 1712: Ways to Split Array Into Three Subarrays
Problem Description
Explanation:
To solve this problem, we can use a two-pointer approach. We initialize the first pointer at the first element and the second pointer at the second element. We then iterate through the array, moving the second pointer to the right while keeping track of the partial sums of the left, mid, and right subarrays.
For each valid split, we can calculate the number of ways to choose the left and mid subarrays by considering all valid starting positions for the mid subarray. To do this efficiently, we can precompute a prefix sum array to quickly calculate the sum of any subarray.
We can then count the number of valid splits and return the result modulo 10^9 + 7.
- Time complexity: O(n) where n is the length of the input array nums.
- Space complexity: O(n) to store the prefix sum array.
:
Solutions
class Solution {
public int waysToSplit(int[] nums) {
int mod = 1000000007;
int n = nums.length;
long[] prefixSum = new long[n];
prefixSum[0] = nums[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i];
}
int result = 0;
long totalSum = prefixSum[n - 1];
for (int i = 0, j = 0, k = 0; i < n - 2; i++) {
while (j <= i || (j < n - 1 && prefixSum[j] < 2 * prefixSum[i])) {
j++;
}
while (k < n - 1 && prefixSum[k] - prefixSum[i] <= totalSum - prefixSum[k]) {
k++;
}
result = (result + Math.max(0, Math.min(j, k) - j)) % mod;
}
return result;
}
}Loading editor...