Number of Ways to Split Array — LeetCode 2270 Python Solution

The 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.

Example

Input

nums = [10,4,-8,7]

Output

2

Explanation

There are three ways of splitting nums into two non-empty parts:

Python solution

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

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2270. Number of Ways to Split Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems