Scale Engineer

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 <= 105
  • -105 <= nums[i] <= 105

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.

class Solution {    public int waysToSplitArray(int[] nums) {        int n = nums.length;        int validSplits = 0;                // Iterate through all possible split points        for (int i = 0; i < n - 1; i++) {            // Use long to prevent integer overflow            long leftSum = 0;            for (int j = 0; j <= i; j++) {                leftSum += nums[j];            }                        long rightSum = 0;            for (int k = i + 1; k < n; k++) {                rightSum += nums[k];            }                        if (leftSum >= rightSum) {                validSplits++;            }        }                return validSplits;    }}

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.

Solutions

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;  }}

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 →

Next problem