You are given a 0-indexed integer array nums of length n.
nums contains a valid split at index i if the following are true:
i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.i. That is, 0 <= i < n - 1.Return the number of valid splits in nums.
Example 1:
Input: nums = [10,4,-8,7] Output: 2 Explanation: There are three ways of splitting nums into two non-empty parts: - Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split. - Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split. - Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split. Thus, the number of valid splits in nums is 2.
Example 2:
Input: nums = [2,3,1,0] Output: 2 Explanation: There are two valid splits in nums: - Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. - Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.
Constraints:
2 <= nums.length <= 105-105 <= nums[i] <= 105This approach involves maintaining a running sum of elements as we iterate through the array and comparing the current left sum with the required condition for the split to be valid.
The function first calculates the total sum of the array. It then iterates over the array, updating the left sum and checking if the condition for a valid split is met. It counts and returns the number of valid splits.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we are using a constant amount of extra space.
This approach consists of a first pass to calculate the total sum and a second pass to check the validity of each possible split by comparing the prefix sum with the remaining sum.
This approach uses two separate loops: one to calculate total sum first, and then a second loop to check conditions for valid splits based on prefix sum calculations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n) where n is the length of the array. |
| Two-Pass Array Approach | Time Complexity: O(n) |
Number of Ways to Split Array - Leetcode 2270 - Python • NeetCodeIO • 5,991 views views
Watch 9 more video solutions →Practice Number of Ways to Split Array with our built-in code editor and test cases.
Practice on FleetCode