Leetcode 1712: Ways to Split Array Into Three Subarrays
You are given an array of non-negative integers. Your task is to count the number of ways the array can be split into three contiguous non-empty subarrays: left, mid, and right. The sum of the elements in the left subarray should be less than or equal to the sum in the mid subarray, and the sum of the mid subarray should be less than or equal to the sum of the right subarray. Return the number of such good splits modulo 10^9 + 7.
Problem
Approach
Steps
Complexity
Input: You are given an integer array 'nums' where each element is a non-negative integer.
Example: [3, 5, 1, 6, 2]
Constraints:
• 3 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^4
Output: Return the number of valid ways to split the array into three subarrays that satisfy the sum conditions, modulo 10^9 + 7.
Example: 2
Constraints:
• The output should be a non-negative integer less than 10^9 + 7.
Goal: Determine the number of valid splits of the array based on the sum conditions.
Steps:
• 1. Calculate the cumulative sums of the elements in the array.
• 2. Use two pointers to explore valid subarray splits that satisfy the condition: left_sum <= mid_sum <= right_sum.
• 3. For each potential left and mid subarray split, calculate how many valid right subarrays exist, and count them.
Goal: Handle the problem efficiently for large arrays while ensuring the result is computed modulo 10^9 + 7.
Steps:
• The array must have at least 3 elements.
• All elements are non-negative integers.
Assumptions:
• The input array is non-empty and has at least 3 elements.
• Input: [1,2,2,2,5,0]
• Explanation: There are three good ways to split the array into three subarrays: [1] [2] [2,2,5,0], [1] [2,2] [2,5,0], and [1,2] [2,2] [5,0]. Each split satisfies the condition left_sum <= mid_sum <= right_sum.
• Input: [3,2,1]
• Explanation: There is no valid way to split the array because no subarray splits satisfy the condition left_sum <= mid_sum <= right_sum.
Approach: To solve this problem efficiently, we need to calculate the number of valid subarray splits that satisfy the sum conditions using two pointers and cumulative sums.
Observations:
• We need to track the sums of potential subarrays efficiently.
• Using a cumulative sum array will allow us to calculate the sum of any subarray in constant time.
Steps:
• 1. Calculate the prefix sum array for the given input array.
• 2. Use a sliding window technique with two pointers to count valid splits.
• 3. Count the number of valid ways to split by iterating over all possible positions of the 'left' subarray and finding the corresponding 'mid' and 'right' subarrays.
Empty Inputs:
• The array will always have at least three elements based on the constraints.
Large Inputs:
• Make sure the algorithm can handle the largest input sizes (up to 10^5 elements).
Special Values:
• Handle cases where all elements are the same value or where some elements are zero.
Constraints:
• The solution must be efficient and handle the upper constraint limits within time limits.
class Solution {
int mod = 1000000007;
public:
int waysToSplit(vector<int>& nums) {
int n = nums.size(), res=0;
partial_sum(nums.begin(), nums.end(), nums.begin());
for(int i = 0, j = 0, k = 0; i < n - 2; i++) {
j = max(i + 1, j);
while(j < n - 1 && 2 * nums[i] > nums[j]) j++;
k = max(j, k);
while(k < n - 1 && nums[k] - nums[i] <= nums[n - 1] - nums[k]) k++;
res = (res + (k - j)) % mod;
}
return res;
}
1 : Class Definition
class Solution {
Defines the `Solution` class that contains the method to solve the problem.
2 : Variable Initialization
int mod = 1000000007;
Initializes a constant `mod` with a large prime number to compute the result modulo this value.
3 : Access Specifier
public:
Marks the following methods as public, allowing them to be accessed outside of the class.
4 : Function Definition
int waysToSplit(vector<int>& nums) {
Defines the function `waysToSplit` that takes a vector `nums` and returns the number of valid ways to split the array into three subarrays.
5 : Variable Initialization
int n = nums.size(), res=0;
Initializes `n` with the size of the input array `nums` and `res` to store the result of the computation.
6 : Prefix Sum Calculation
partial_sum(nums.begin(), nums.end(), nums.begin());
Calculates the prefix sum of the array `nums` and stores the cumulative sum in the same vector, which allows for efficient range sum calculations.
7 : Outer Loop
for(int i = 0, j = 0, k = 0; i < n - 2; i++) {
Begins a loop through the array to consider each possible starting index for the first subarray.
8 : Update j
j = max(i + 1, j);
Updates the index `j` to ensure it is at least one position ahead of `i`.
9 : Inner Loop
while(j < n - 1 && 2 * nums[i] > nums[j]) j++;
Advances the index `j` while the sum of the first subarray (`nums[i]`) is greater than the sum of the second subarray (`nums[j]`).
10 : Update k
k = max(j, k);
Ensures that `k` is at least as large as `j`, maintaining the correct relationship between the indices.
11 : Second Inner Loop
while(k < n - 1 && nums[k] - nums[i] <= nums[n - 1] - nums[k]) k++;
Advances the index `k` to maintain the condition that the difference between the second and third subarray sums is non-negative.
12 : Result Update
res = (res + (k - j)) % mod;
Updates the result `res` by adding the number of valid splits found in the current iteration, taking the modulo `mod` to prevent overflow.
13 : Return Result
return res;
Returns the final result, which is the total number of valid ways to split the array into three subarrays.
Best Case: O(n), where n is the length of the input array.
Average Case: O(n), as we iterate through the array and calculate valid splits in a linear pass.
Worst Case: O(n), as we perform a linear scan with two pointers over the array.
Description: The solution uses a linear scan to find all valid splits, making the time complexity O(n).
Best Case: O(n), if the input array is large.
Worst Case: O(n), due to the space needed for the cumulative sum array.
Description: The space complexity is O(n) because we store the cumulative sums of the array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus