Number of Ways to Split Array

Medium
1153.

Number of Ways to Split Array

Number of Ways to Split Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Microsoft interviews.

A split of the integer array nums (length n) at index i, where 0 <= i < n - 1, cuts it into a left part nums[0..i] and a right part nums[i+1..n-1]. Both parts are therefore non-empty.

The split is valid when the sum of the left part is greater than or equal to the sum of the right part.

Return the number of valid splits.

Example 1

Input
nums = [4,-2,6,-3]
Output
2
Explanation
Cutting after index 0 gives 4 vs 1, and after index 2 gives 8 vs -3. Cutting after index 1 gives 2 vs 3, which is not valid.

Example 2

Input
nums = [1,1]
Output
1

Example 3

Input
nums = [-5,3,3]
Output
0

Constraints

  • 2 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var waysToSplitArray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Ways to Split Array — Problem & Solution

Number of Ways to Split Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Ways to Split Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A split of the integer array nums (length n) at index i, where 0 <= i < n - 1, cuts it into a left part nums[0..i] and a right part nums[i+1..n-1]. Both parts are therefore non-empty.

The split is valid when the sum of the left part is greater than or equal to the sum of the right part.

Return the number of valid splits.

Example 1

Input: nums = [4,-2,6,-3]
Output: 2
Explanation: Cutting after index 0 gives 4 vs 1, and after index 2 gives 8 vs -3. Cutting after index 1 gives 2 vs 3, which is not valid.

Example 2

Input: nums = [1,1]
Output: 1

Example 3

Input: nums = [-5,3,3]
Output: 0

Constraints

  • 2 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5

Hints for Number of Ways to Split Array

  1. Hint 1

    Summing both sides from scratch for every cut is quadratic.

  2. Hint 2

    If you know the total, the right part's sum is total - left.

  3. Hint 3

    Sweep once with a running left sum (64-bit: it can reach 10^10 in magnitude) and stop before the last index.

How to solve Number of Ways to Split Array

The right part's sum is always the total minus the left part's sum, so a single prefix sweep checks every cut in O(1).

Approach

  1. Compute total, the sum of the whole array, in a 64-bit integer.
  2. Sweep i from 0 to n - 2, adding nums[i] to left.
  3. Count the cut when left >= total - left.
  4. Return the count.

Why it works

At cut i the left part is exactly the prefix nums[0..i] and the right part is everything else, whose sum is total - left. Every legal cut is visited once, and the last index is excluded because the right part must be non-empty.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The loop stops at n - 2; cutting after the last element leaves the right side empty.
  • Negative numbers mean the left sum is not monotonic — do not stop early or binary search.
  • Sums reach 10^10 in magnitude, beyond 32-bit range.

Reference solution

Python

from typing import List

def waysToSplitArray(nums: List[int]) -> int:
    total = sum(nums)
    left = 0
    ways = 0
    for i in range(len(nums) - 1):
        left += nums[i]
        if left >= total - left:
            ways += 1
    return ways

Java

public static int waysToSplitArray(int[] nums) {
    long total = 0;
    for (int x : nums) total += x;
    long left = 0;
    int ways = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        left += nums[i];
        if (left >= total - left) ways++;
    }
    return ways;
}

C++

int waysToSplitArray(vector<int>& nums) {
    long long total = 0;
    for (int x : nums) total += x;
    long long left = 0;
    int ways = 0;
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        left += nums[i];
        if (left >= total - left) ways++;
    }
    return ways;
}

JavaScript

var waysToSplitArray = function(nums) {
    var total = 0;
    for (var i = 0; i < nums.length; i++) total += nums[i];
    var left = 0, ways = 0;
    for (var j = 0; j < nums.length - 1; j++) {
        left += nums[j];
        if (left >= total - left) ways++;
    }
    return ways;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum