LeetCode 2270 - Number of Ways to Split Array

LeetCode Problem 2270

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine the number of ways to split a given 0-indexed array nums into two non-empty contiguous subarrays such that the sum of the first part is greater than or equal to the sum of the second part. Formally, a split at index i is valid if sum(nums[0:i+1]) >= sum(nums[i+1:n]) and 0 <= i < n-1 to ensure there is at least one element in the right subarray.

The input nums is an integer array with length n between 2 and 10^5, and elements can range from -10^5 to 10^5. The output is a single integer representing the count of valid split indices.

Key observations include: we need a way to efficiently compute subarray sums because a naive summation for each split would be too slow for large arrays. Negative numbers are allowed, which means that sums can decrease or increase unpredictably, so we cannot assume sorted or positive values. The constraints guarantee that there is always at least one possible split because n >= 2.

Edge cases include arrays with all negative numbers, arrays with only two elements, and arrays with alternating large positive and negative values that could affect the sum comparisons.

Approaches

The brute-force approach is straightforward. For each valid split index i from 0 to n-2, calculate the sum of the left subarray nums[0:i+1] and the sum of the right subarray nums[i+1:n], then compare. This approach is correct because it explicitly checks the split condition for every index. However, its time complexity is O(n^2) due to recomputing sums repeatedly, which is infeasible for n = 10^5.

The optimal approach leverages prefix sums. First, compute the total sum of the array. Then, iterate through the array, maintaining a running sum for the left subarray. The right subarray sum can then be computed as total_sum - left_sum in O(1). Each comparison left_sum >= right_sum can be done in constant time, giving an overall linear time complexity O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Computes left and right sums for each split explicitly
Optimal	O(n)	O(1)	Uses running sum and total sum to compute right subarray sum efficiently

Algorithm Walkthrough

1. Compute the total sum of the array nums and store it in total_sum. This represents the sum of all elements.
2. Initialize left_sum to 0 and a counter valid_splits to 0.
3. Iterate over the array with index i from 0 to n-2. For each element, add nums[i] to left_sum.
4. Compute right_sum as total_sum - left_sum. This gives the sum of the remaining elements to the right of index i.
5. If left_sum >= right_sum, increment valid_splits.
6. Continue until the end of the loop. Return valid_splits as the final answer.

Why it works: At each step, left_sum maintains the sum of elements up to the current index, and right_sum calculates the remaining sum efficiently using the total sum. The comparison checks the condition exactly as specified in the problem, ensuring correctness.

Python Solution

from typing import List

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0
        valid_splits = 0
        
        for i in range(len(nums) - 1):
            left_sum += nums[i]
            right_sum = total_sum - left_sum
            if left_sum >= right_sum:
                valid_splits += 1
        
        return valid_splits

In the implementation, total_sum stores the sum of the entire array. The loop iterates until n-2 because the last element cannot be a valid split. At each iteration, we update left_sum and calculate right_sum using the total sum. If the condition holds, we increment the valid_splits counter. Finally, we return the count.

Go Solution

func waysToSplitArray(nums []int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }

    leftSum := 0
    validSplits := 0

    for i := 0; i < len(nums)-1; i++ {
        leftSum += nums[i]
        rightSum := totalSum - leftSum
        if leftSum >= rightSum {
            validSplits++
        }
    }

    return validSplits
}

In Go, we use a standard for loop to compute totalSum first, then iterate through the array up to len(nums)-1. We use integer arithmetic and slices efficiently, keeping leftSum and rightSum updated at each step. This implementation mirrors the Python logic.

Worked Examples

Example 1: nums = [10,4,-8,7]

i	left_sum	right_sum	Condition (>=)	valid_splits
0	10	3	True	1
1	14	-1	True	2
2	6	7	False	2

Final answer: 2

Example 2: nums = [2,3,1,0]

i	left_sum	right_sum	Condition (>=)	valid_splits
0	2	4	False	0
1	5	1	True	1
2	6	0	True	2

Final answer: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Sum of array takes O(n) and one pass to check splits is O(n), so total O(n)
Space	O(1)	Only a few integer variables are used, no extra data structures

The reasoning is that we avoid recomputing sums repeatedly by using a running sum and the total sum. Memory usage is constant regardless of input size.

Test Cases

# Provided examples
assert Solution().waysToSplitArray([10,4,-8,7]) == 2  # mix of positive and negative
assert Solution().waysToSplitArray([2,3,1,0]) == 2    # all positive numbers

# Edge cases
assert Solution().waysToSplitArray([1,1]) == 1        # minimum length array
assert Solution().waysToSplitArray([-1,-2,-3,-4]) == 3 # all negative numbers
assert Solution().waysToSplitArray([5, -1, 2, -2, 3]) == 3 # mixed numbers
assert Solution().waysToSplitArray([100000, -100000]) == 1 # large numbers with zero sum

Test	Why
[10,4,-8,7]	Validates mix of positive and negative numbers
[2,3,1,0]	Validates small positive numbers
[1,1]	Tests minimum array length
[-1,-2,-3,-4]	Tests all negative numbers
[5,-1,2,-2,3]	Tests mixed numbers affecting sums
[100000,-100000]	Tests large numbers, edge of constraints

Edge Cases

First, the smallest possible array with two elements [a, b]. This is an edge case because there is only one possible split. The code correctly handles it by iterating only to n-2, and the single comparison ensures correctness.

Second, arrays with all negative numbers, such as [-5, -2, -3, -1]. Negative sums can decrease as we include more elements in left_sum. The algorithm correctly computes left_sum and right_sum using signed integers, ensuring correct comparisons even when sums are negative.

Third, arrays where sums oscillate due to alternating positive and negative numbers, e.g., [5, -5, 5, -5, 5]. A naive implementation might fail if it assumes sums increase monotonically. The prefix-sum approach handles this correctly because each comparison is made dynamically with the running sum and total sum, independent of the pattern of numbers.