#2270

Medium

LeetCode Problem Workspace

Number of Ways to Split Array

Count all valid ways to split a 0-indexed integer array into two non-empty parts using array plus prefix sum logic efficiently.

array prefix sum

Problem Statement

You are given a 0-indexed integer array nums of length n. A split occurs at index i if the sum of the first i+1 elements is greater than or equal to the sum of the remaining elements. Return the total number of valid splits in nums.

For example, nums = [10,4,-8,7] has valid splits at indices 0 and 1 because the sum of the left partition is greater than or equal to the right. Ensure that both parts after a split are non-empty. Constraints: 2 <= nums.length <= 105, -105 <= nums[i] <= 105.

Examples

Example 1

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

Output: 2

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

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 Approach

Compute Prefix Sum

Generate a running total array to efficiently track sums of the first i elements. This reduces repeated summation and aligns with the array plus prefix sum pattern.

Iterate and Compare Partitions

For each index i from 0 to n-2, compare the prefix sum of the left part with the remaining sum. Increment a counter when the left sum is greater than or equal to the right sum to capture valid splits.

Optimize Space Usage

Instead of storing the full prefix sum array, maintain a single left sum variable and compute the right sum dynamically as total sum minus left sum. This achieves O(1) extra space while following the prefix sum trade-off.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each element is processed once for prefix sums and comparisons. Space complexity is O(1) if using a running sum variable instead of a full prefix sum array.

What Interviewers Usually Probe

Focus on array plus prefix sum pattern rather than naive double loops.
Check that both left and right partitions are non-empty when identifying valid splits.
Optimize for linear time; repeated summation signals inefficiency.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude the last index since the right partition must be non-empty.
Recomputing sums for every split instead of using a prefix sum approach.
Using extra space unnecessarily by storing all prefix sums instead of running totals.

Follow-up variants

Count splits where left sum must strictly exceed right sum instead of >=.
Allow multiple splits per index if the array has repeated values affecting sums.
Compute the maximum number of splits achievable in any continuous subarray.

FAQ

What is the main idea behind Number of Ways to Split Array?

Use prefix sums to efficiently determine at each index if the left sum is greater than or equal to the right sum, counting valid splits.

Can we solve this without extra space?

Yes, by maintaining a running left sum and computing the right sum as total minus left sum, achieving O(1) extra space.

Why is the array plus prefix sum pattern important?

It allows computing partition sums in constant time per index, avoiding repeated summations and ensuring linear performance.

What common mistakes should I avoid?

Do not include the last index for splitting, avoid recomputing sums in loops, and ensure both partitions are non-empty.

How does GhostInterview help with this problem?

GhostInterview guides through prefix sum calculations, dynamic comparisons, and highlights miscounted splits to efficiently solve the problem.

terminal

Solution

Solution 1: Prefix Sum

First, we calculate the total sum $s$ of the array $\textit{nums}$. Then, we traverse the first $n-1$ elements of the array $\textit{nums}$, using the variable $t$ to record the prefix sum. If $t \geq s - t$, we increment the answer by one.

1

2

3

4

5

6

7

8

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

Continue Practicing

#2271 maximum white tiles covered by a carpet #2281 sum of total strength of wizards #2256 minimum average difference