Number of Ways to Split Array solution and explanation
Google
9 more videos on this problem
Number of Ways to Split Array - Leetcode 2270 - PythonNeetCodeIO · 6:38 · 7K views
Number of Ways to Split Array | Simple Thought Process | Leetcode 2270 | codestorywithMIKcodestorywithMIK · 12:50 · 6K views
Number of Ways to Split Array | Leetcode 2270Techdose · 8:53 · 2K views
2270. Number of Ways to Split Array | leetcode daily challenge | dsaShashCode · 11:44 · 1K views
2270. Number of Ways to Split Array | Prefix SumsAryan Mittal · 7:15 · 803 views
LeetCode 2270 Number of Ways to Split Array | Prefix Sum | Asked in AmazonCode Harmony · 11:39 · 102 views
Number of Ways to Split Array | LC 2270 | JavaCS with Andry · 7:56 · 74 views
LeetCode 2270. Number of Ways to Split Array [Medium]Programming Interviews Preparation · 2:57 · 67 views
Number of Ways to Split Array - Python || O(n) time & O(1) space || LeetCode 2270codegrind · 3:02 · 65 views
LeetCode 2270 - Number of Ways to Split Array - GoAlpha-Code · 7:27 · 49 views
The problem
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 + 1elements is greater than or equal to the sum of the lastn - i - 1elements. - 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.
def valid_splits(nums):
total_sum, left_sum, valid_count = sum(nums), 0, 0
for i in range(len(nums) - 1):
left_sum += nums[i]
if left_sum >= (total_sum - left_sum):
valid_count += 1
return valid_count
nums = [10, 4, -8, 7]
print(valid_splits(nums)) # Output: 2public class Solution {
public static int validSplits(int[] nums) {
int totalSum = 0, leftSum = 0, validCount = 0;
for (int num : nums) totalSum += num;
for (int i = 0; i < nums.length - 1; i++) {
leftSum += nums[i];
if (leftSum >= totalSum - leftSum) {
validCount++;
}
}
return validCount;
}
public static void main(String[] args) {
int[] nums = {10, 4, -8, 7};
System.out.println(validSplits(nums)); // Output: 2
}
}#include <iostream>
#include <vector>
using namespace std;
int validSplits(vector<int>& nums) {
int totalSum = 0, leftSum = 0, validCount = 0;
for(int num : nums) totalSum += num;
for(int i = 0; i < nums.size() - 1; i++) {
leftSum += nums[i];
if(leftSum >= totalSum - leftSum) {
validCount++;
}
}
return validCount;
}
int main() {
vector<int> nums = {10, 4, -8, 7};
cout << validSplits(nums) << endl; // Output: 2
return 0;
}function validSplits(nums) {
let totalSum = nums.reduce((a, b) => a + b, 0);
let leftSum = 0;
let validCount = 0;
for (let i = 0; i < nums.length - 1; i++) {
leftSum += nums[i];
if (leftSum >= (totalSum - leftSum)) {
validCount++;
}
}
return validCount;
}
const nums = [10, 4, -8, 7];
console.log(validSplits(nums)); // Output: 2#include <stdio.h>
int validSplits(int* nums, int numsSize) {
int totalSum = 0, leftSum = 0, validCount = 0;
for(int i = 0; i < numsSize; i++) {
totalSum += nums[i];
}
for(int i = 0; i < numsSize - 1; i++) {
leftSum += nums[i];
if(leftSum >= (totalSum - leftSum)) {
validCount++;
}
}
return validCount;
}
int main() {
int nums[] = {10, 4, -8, 7};
int result = validSplits(nums, 4);
printf("%d\n", result); // Output: 2
return 0;
}using System;
public class Solution {
public int ValidSplits(int[] nums) {
int totalSum = 0, leftSum = 0, validCount = 0;
foreach (int num in nums) totalSum += num;
for (int i = 0; i < nums.Length - 1; i++) {
leftSum += nums[i];
if (leftSum >= totalSum - leftSum) {
validCount++;
}
}
return validCount;
}
public static void Main(string[] args) {
int[] nums = {10, 4, -8, 7};
Solution sol = new Solution();
Console.WriteLine(sol.ValidSplits(nums)); // Output: 2
}
}The Python version of the solution makes use of the sum function to calculate the total sum initially. As it iterates through the list, it checks the validity of splits by maintaining a growing left sum.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def valid_splits(nums):
total_sum = sum(nums)
left_sum, valid_count = 0, 0
for i in range(len(nums) - 1):
left_sum += nums[i]
if left_sum >= (total_sum - left_sum):
valid_count += 1
return valid_count
nums = [2, 3, 1, 0]
print(valid_splits(nums)) # Output: 2public class Solution {
public static int validSplits(int[] nums) {
int totalSum = 0;
for (int num : nums) totalSum += num;
int leftSum = 0, validCount = 0;
for (int i = 0; i < nums.length - 1; i++) {
leftSum += nums[i];
if (leftSum >= totalSum - leftSum) {
validCount++;
}
}
return validCount;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 0};
System.out.println(validSplits(nums)); // Output: 2
}
}#include <iostream>
#include <vector>
using namespace std;
int validSplits(vector<int>& nums) {
int totalSum = 0;
for(int num : nums) totalSum += num;
int leftSum = 0, validCount = 0;
for(int i = 0; i < nums.size() - 1; i++) {
leftSum += nums[i];
if(leftSum >= totalSum - leftSum) {
validCount++;
}
}
return validCount;
}
int main() {
vector<int> nums = {2, 3, 1, 0};
cout << validSplits(nums) << endl; // Output: 2
return 0;
}function validSplits(nums) {
let totalSum = nums.reduce((a, b) => a + b, 0);
let leftSum = 0;
let validCount = 0;
for (let i = 0; i < nums.length - 1; i++) {
leftSum += nums[i];
if (leftSum >= (totalSum - leftSum)) {
validCount++;
}
}
return validCount;
}
const nums = [2, 3, 1, 0];
console.log(validSplits(nums)); // Output: 2#include <stdio.h>
int validSplits(int* nums, int numsSize) {
int totalSum = 0;
for (int i = 0; i < numsSize; i++) {
totalSum += nums[i];
}
int leftSum = 0, validCount = 0;
for (int i = 0; i < numsSize - 1; i++) {
leftSum += nums[i];
if (leftSum >= (totalSum - leftSum)) {
validCount++;
}
}
return validCount;
}
int main() {
int nums[] = {2, 3, 1, 0};
int result = validSplits(nums, 4);
printf("%d\n", result); // Output: 2
return 0;
}using System;
public class Solution {
public int ValidSplits(int[] nums) {
int totalSum = 0;
foreach (int num in nums) totalSum += num;
int leftSum = 0, validCount = 0;
for (int i = 0; i < nums.Length - 1; i++) {
leftSum += nums[i];
if (leftSum >= totalSum - leftSum) {
validCount++;
}
}
return validCount;
}
public static void Main(string[] args) {
int[] nums = {2, 3, 1, 0};
Solution sol = new Solution();
Console.WriteLine(sol.ValidSplits(nums)); // Output: 2
}
}The Python solution first calculates the total sum, and then uses it in a second loop to determine valid split conditions at each possible position.
Time Complexity: O(n)
Space Complexity: O(1)
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).
function waysToSplitArray(nums: number[]): number {
const s = nums.reduce((acc, cur) => acc + cur, 0);
let [ans, t] = [0, 0];
for (const x of nums.slice(0, -1)) {
t += x;
if (t >= s - t) {
++ans;
}
}
return ans;
}func waysToSplitArray(nums []int) (ans int) {
var s, t int
for _, x := range nums {
s += x
}
for _, x := range nums[:len(nums)-1] {
t += x
if t >= s-t {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n) |
| Two-Pass Array Approach | Time Complexity: O(n) |
| Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Prefix Array | O(n) | O(n) | Good for learning prefix sums or when explicit prefix storage is useful for multiple queries |
| Running Prefix Sum | O(n) | O(1) | Optimal approach for interviews and production code with minimal memory usage |
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.