Number of Ways to Split Array

Med

#2068Time: O(n^2), where n is the number of elements in `nums`. The outer loop runs `n-1` times. Inside the loop, calculating the left and right sums takes `O(n)` time in total. This results in a quadratic time complexity, which is too slow for the given constraints.Space: O(1). We only use a few variables to store the sums and the count, which does not depend on the input size.

Patterns

Prefix Sum

Data structures

Array

Prompt

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem description into code. We iterate through all possible split points and, for each point, we calculate the sum of the left and right subarrays independently using nested loops. We then compare these sums to check if the split is valid.

Algorithm

Initialize a counter validSplits to 0.
Iterate through each possible split index i from 0 to n-2, where n is the length of the array.
For each i, calculate leftSum, the sum of elements from nums[0] to nums[i].
For the same i, calculate rightSum, the sum of elements from nums[i+1] to nums[n-1].
If leftSum is greater than or equal to rightSum, increment validSplits.
After the loop finishes, return validSplits.

Walkthrough

The core idea is to check every possible split index i from 0 to n-2. For each i, we need to compute two sums: leftSum (sum of elements from index 0 to i) and rightSum (sum of elements from index i+1 to n-1). We can use two separate loops to calculate these sums. After computing both sums, we check if leftSum >= rightSum. If this condition holds, we increment a counter for valid splits. This process is repeated for all possible values of i.

1class Solution {2    public int waysToSplitArray(int[] nums) {3        int n = nums.length;4        int validSplits = 0;5        6        // Iterate through all possible split points7        for (int i = 0; i < n - 1; i++) {8            // Use long to prevent integer overflow9            long leftSum = 0;10            for (int j = 0; j <= i; j++) {11                leftSum += nums[j];12            }13            14            long rightSum = 0;15            for (int k = i + 1; k < n; k++) {16                rightSum += nums[k];17            }18            19            if (leftSum >= rightSum) {20                validSplits++;21            }22        }23        24        return validSplits;25    }26}

Note the use of long for the sums to avoid potential integer overflow, as the sum of elements can exceed the capacity of a standard 32-bit integer.

Complexity

Time

O(n^2), where n is the number of elements in `nums`. The outer loop runs `n-1` times. Inside the loop, calculating the left and right sums takes `O(n)` time in total. This results in a quadratic time complexity, which is too slow for the given constraints.

Space

O(1). We only use a few variables to store the sums and the count, which does not depend on the input size.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem statement.

Cons

Highly inefficient due to redundant calculations.
Will result in a 'Time Limit Exceeded' (TLE) error for large input arrays.

A more efficient approach avoids recalculating sums from scratch. We can pre-calculate the total sum of the array. Then, we can iterate through the array once, maintaining a running sum for the left part (leftSum). The sum of the right part (rightSum) can be found in constant time by subtracting leftSum from the totalSum.

Algorithm

Calculate the totalSum of all elements in the array. Use a 64-bit integer (long) to avoid overflow.
Initialize validSplits = 0 and leftSum = 0 (as a long).
Iterate with an index i from 0 to n-2.
In each iteration, update leftSum by adding nums[i].
Calculate rightSum by subtracting the current leftSum from totalSum.
If leftSum >= rightSum, increment validSplits.
Return validSplits after the loop.

Walkthrough

The bottleneck in the brute-force method is the repeated summation. We can optimize this by observing that if we know the leftSum and the totalSum of the array, the rightSum is simply totalSum - leftSum. The algorithm proceeds as follows:

First, compute the totalSum of all elements in the nums array. This requires a single pass. It's crucial to use a long data type for the sum to prevent overflow.
Initialize a validSplits counter to 0 and a leftSum to 0.
Iterate from i = 0 to n-2. In each step: a. Add nums[i] to leftSum. b. Calculate rightSum as totalSum - leftSum. c. Compare leftSum and rightSum. If leftSum >= rightSum, increment validSplits.
After iterating through all possible split points, return the validSplits count. This approach reduces the time complexity significantly by eliminating the nested loops.

1class Solution {2    public int waysToSplitArray(int[] nums) {3        int n = nums.length;4        5        // Use long to prevent integer overflow6        long totalSum = 0;7        for (int num : nums) {8            totalSum += num;9        }10        11        int validSplits = 0;12        long leftSum = 0;13        14        // Iterate through all possible split points15        for (int i = 0; i < n - 1; i++) {16            // Add current element to the left sum17            leftSum += nums[i];18            19            // Calculate the right sum20            long rightSum = totalSum - leftSum;21            22            // Check the condition for a valid split23            if (leftSum >= rightSum) {24                validSplits++;25            }26        }27        28        return validSplits;29    }30}

Complexity

Time

O(n), where n is the number of elements in `nums`. We make two passes through the array: one to calculate the total sum and another to check for valid splits. This is linear time complexity, which is very efficient.

Space

O(1). We only use a few variables (`totalSum`, `leftSum`, `validSplits`) to store intermediate values, requiring constant extra space.

Trade-offs

Pros

Optimal time complexity, solving the problem efficiently within the given constraints.
Space efficient, using only constant extra memory.

Cons

Requires careful handling of potential integer overflow by using a larger data type like long for sums.

Solutions

Solution

1class Solution {2public3  int waysToSplitArray(int[] nums) {4    long s = 0;5    for (int v : nums) {6      s += v;7    }8    int ans = 0;9    long t = 0;10    for (int i = 0; i < nums.length - 1; ++i) {11      t += nums[i];12      if (t >= s - t) {13        ++ans;14      }15    }16    return ans;17  }18}

1class Solution {2public:3  int waysToSplitArray(vector<int> &nums) {4    long long s = accumulate(nums.begin(), nums.end(), 0ll);5    long long t = 0;6    int ans = 0;7    for (int i = 0; i < nums.size() - 1; ++i) {8      t += nums[i];9      ans += t >= s - t;10    }11    return ans;12  }13};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem