Skip to main content
Talentd

Number of Ways to Split Array - Solution & Explanation

MediumArrayPrefix Sum14 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array nums. A split index divides the array into a left subarray [0..i] and a right subarray [i+1..n-1]. A split is valid when the sum of the left part is greater than or equal to the sum of the right part. The task is to count how many such split positions exist.

Approach 1: Two-Pass Prefix Array (O(n) time, O(n) space)

This approach builds a prefix sum array where prefix[i] stores the sum of elements from index 0 to i. First iterate through the array to compute prefix sums. Then iterate again and evaluate each possible split. For a split at i, the left sum is prefix[i] and the right sum is prefix[n-1] - prefix[i]. If prefix[i] >= prefix[n-1] - prefix[i], the split is valid. This approach is straightforward and easy to reason about because both subarray sums are retrieved in constant time. It’s a good starting point when working with prefix sum problems on arrays.

Approach 2: Running Prefix Sum (O(n) time, O(1) space)

The prefix array can be eliminated by computing the total sum first. Iterate through the array once to get totalSum. Then iterate again while maintaining a running prefix sum leftSum. At each index i, the right subarray sum becomes totalSum - leftSum. If leftSum >= totalSum - leftSum, the split is valid. This works because every valid split simply compares the accumulated left sum with the remaining sum of the array. The algorithm only tracks a few variables, so it reduces space usage to constant while keeping the same linear runtime.

The key insight is that every split can be evaluated using prefix sums. Instead of recomputing sums for each partition (which would lead to O(n²) time), prefix accumulation lets you evaluate each split in constant time while scanning the array once.

Recommended for interviews: The running prefix sum solution is the expected answer. Interviewers want to see that you recognize this as a prefix sum pattern and avoid repeated summation. Mentioning the prefix array approach first shows understanding of the concept, while optimizing it to O(1) space demonstrates stronger problem-solving skills.

Approach 1: Prefix Sum Approach

This approach involves maintaining a running sum of elements as we iterate through the array and comparing the current left sum with the required condition for the split to be valid.

The function first calculates the total sum of the array. It then iterates over the array, updating the left sum and checking if the condition for a valid split is met. It counts and returns the number of valid splits.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Two-Pass Array Approach

This approach consists of a first pass to calculate the total sum and a second pass to check the validity of each possible split by comparing the prefix sum with the remaining sum.

This approach uses two separate loops: one to calculate total sum first, and then a second loop to check conditions for valid splits based on prefix sum calculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Prefix Sum

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

After the traversal, we return the answer.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum Approach

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we are using a constant amount of extra space.

Two-Pass Array Approach

Time Complexity: O(n)
Space Complexity: O(1)

Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pass Prefix ArrayO(n)O(n)Good for learning prefix sums or when explicit prefix storage is useful for multiple queries
Running Prefix SumO(n)O(1)Optimal approach for interviews and production code with minimal memory usage

Video Solution

Number of Ways to Split Array - Leetcode 2270 - Python • NeetCodeIO • 7,089 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Ways to Split Array easy or hard?
LeetCode classifies this problem as Medium. The logic is straightforward once you recognize the prefix sum pattern, but identifying that you can compare prefix and remaining sums in a single pass requires familiarity with array accumulation techniques.
Number of Ways to Split Array Python/Java solution
In Python or Java, compute the total sum using a loop or built-in function, then iterate through the array while maintaining a running prefix sum. For each index before the last element, check if leftSum >= totalSum - leftSum and increment the answer. The implementation runs in O(n) time and uses constant extra space.
How to solve Number of Ways to Split Array in O(n)?
Compute the total array sum first. Then iterate through the array while accumulating a running prefix sum. At each index i, calculate the right side sum as totalSum - leftSum. If leftSum >= rightSum, increment the count of valid splits. This single-pass check after computing the total sum gives an O(n) time solution.
What is the best approach for Number of Ways to Split Array?
The optimal approach uses a running prefix sum. First compute the total sum of the array, then iterate while maintaining the left prefix sum. For each index, compare leftSum with totalSum - leftSum. This checks whether the left subarray sum is greater than or equal to the right subarray sum. The algorithm runs in O(n) time and O(1) extra space.
Is Number of Ways to Split Array asked at Google/Amazon/Meta?
Prefix sum and array partitioning problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve comparing prefix and suffix sums are especially common because they test linear-time reasoning and efficient accumulation techniques.
What data structure is used in Number of Ways to Split Array?
The main technique relies on prefix sums over an array. No complex data structures are required. The optimal implementation only tracks integer variables for the total sum and the running left sum while iterating through the array.
What is the time complexity of Number of Ways to Split Array?
The optimal solution runs in O(n) time because the array is scanned at most twice: once to compute the total sum and once to evaluate valid split positions. Each split check is constant time. Space complexity can be O(1) if you use a running prefix sum, or O(n) if a full prefix array is stored.

Ready to solve this problem?

Practice Number of Ways to Split Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Pivot Index

Next

Find the Middle Index in Array