Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2270.html

2270. Number of Ways to Split Array

  • Difficulty: Medium.
  • Related Topics: Array, Prefix Sum.
  • Similar Questions: Split Array Largest Sum, Find Pivot Index, Ways to Split Array Into Three Subarrays, Find the Middle Index in Array, Partition Array Into Two Arrays to Minimize Sum Difference, Minimum Average Difference.

Problem

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:

  • The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.

  • There is at least one element to the right of 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] <= 105

Solution (Java, C++, Python)

  • class Solution {
    public int waysToSplitArray(int[] nums) {
        long leftSum = 0;
        long rightSum = 0;
        for (int i : nums) {
            rightSum += i;
        }
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            rightSum -= nums[i];
            leftSum += nums[i];
            if (leftSum >= rightSum) {
                count++;
            }
        }
        return count;
    }
}

############

class Solution {
    public int waysToSplitArray(int[] nums) {
        long s = 0;
        for (int v : nums) {
            s += v;
        }
        int ans = 0;
        long t = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            t += nums[i];
            if (t >= s - t) {
                ++ans;
            }
        }
        return ans;
    }
}

  • class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        s = sum(nums)
        ans = t = 0
        for v in nums[:-1]:
            t += v
            if t >= s - t:
                ans += 1
        return ans

############

# 2270. Number of Ways to Split Array
# https://leetcode.com/problems/number-of-ways-to-split-array/

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        prefix = [0] + list(accumulate(nums))
        total = sum(nums)
        n = len(nums)
        res = 0
        
        for i in range(n - 1):
            left = prefix[i + 1]
            right = prefix[-1] - prefix[i + 1]
            
            if left >= right:
                res += 1
        
        return res


  • class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        long long s = accumulate(nums.begin(), nums.end(), 0ll);
        long long t = 0;
        int ans = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            t += nums[i];
            ans += t >= s - t;
        }
        return ans;
    }
};

  • func waysToSplitArray(nums []int) int {
	s := 0
	for _, v := range nums {
		s += v
	}
	ans, t := 0, 0
	for _, v := range nums[:len(nums)-1] {
		t += v
		if t >= s-t {
			ans++
		}
	}
	return ans
}

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions