Number of Ways to Split Array - Practice Coding Problems

Number of Ways to Split Array - 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 + 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.

Input & Output

Example 1 — Basic Array

$ Input: nums = [10,4,-8,7]

› Output: 2

💡 Note: Split at index 0: [10] vs [4,-8,7] → 10 >= 3 ✓. Split at index 1: [10,4] vs [-8,7] → 14 >= -1 ✓. Split at index 2: [10,4,-8] vs [7] → 6 < 7 ✗. Total: 2 valid splits.

Example 2 — All Positive

$ Input: nums = [2,3,1,0]

› Output: 2

💡 Note: Split at index 0: [2] vs [3,1,0] → 2 < 4 ✗. Split at index 1: [2,3] vs [1,0] → 5 >= 1 ✓. Split at index 2: [2,3,1] vs [0] → 6 >= 0 ✓. Total: 2 valid splits.

Example 3 — Minimum Size

$ Input: nums = [1,1]

› Output: 1

💡 Note: Only one possible split at index 0: [1] vs [1] → 1 >= 1 ✓. Total: 1 valid split.

Constraints

2 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [10, 4, -8, 7] with indices 0 to 3

Check Splits

Test each valid split position (0 to n-2)

Count Valid

Count splits where left_sum >= right_sum

Key Takeaway

🎯 Key Insight: Use prefix sum to avoid recalculating sums for each split position

Asked in

M Microsoft 15 G Google 12 a Amazon 8

The key insight is to avoid recalculating sums by using prefix sum technique. Instead of computing left and right sums from scratch for each split, calculate the total sum once, then maintain a running left sum and derive the right sum as total_sum - left_sum. Best approach is Prefix Sum with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Calculate Sums for Each Split	O(n²)	O(1)	For each possible split position, calculate left and right sums separately
Prefix Sum - Single Pass Optimization	O(n)	O(1)	Pre-calculate total sum, then use running left sum to find right sum efficiently

Brute Force - Calculate Sums for Each Split — Algorithm Steps

Step 1: For each index i from 0 to n-2
Step 2: Calculate sum of elements from 0 to i (left side)
Step 3: Calculate sum of elements from i+1 to n-1 (right side)
Step 4: If left_sum >= right_sum, increment count

Visualization

Tap to expand

Step-by-Step Walkthrough

Split at index 0

Left: [10], Right: [4,-8,7] → 10 >= 3 ✓

Split at index 1

Left: [10,4], Right: [-8,7] → 14 >= -1 ✓

Split at index 2

Left: [10,4,-8], Right: [7] → 6 < 7 ✗

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int count = 0;
    
    for (int i = 0; i < numsSize - 1; i++) {
        long long leftSum = 0;
        long long rightSum = 0;
        
        // Calculate left sum
        for (int j = 0; j <= i; j++) {
            leftSum += nums[j];
        }
        
        // Calculate right sum
        for (int j = i + 1; j < numsSize; j++) {
            rightSum += nums[j];
        }
        
        if (leftSum >= rightSum) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array
    int nums[10000];
    int size = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n-1 times, inner sum calculations take O(n) each

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables for counting and sum calculations

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Calculate Sums for Each Split — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler