Split Array with Equal Sum - Practice Coding Problems

Split Array with Equal Sum - Problem

Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions:

0 < i, i + 1 < j, j + 1 < k < n - 1
The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.

A subarray (l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.

Note: The array is split into four parts by three dividers at positions i, j, and k.

Input & Output

Example 1 — Valid Split Exists

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

› Output: true

💡 Note: With i=1, j=3, k=5: part1=[1] sum=1, part2=[1] sum=1, part3=[1] sum=1, part4=[1] sum=1. All sums equal 1.

Example 2 — No Valid Split

$ Input: nums = [1,2,3,4,5,6,7]

› Output: false

💡 Note: No triplet (i,j,k) can create four subarrays with equal sums from this ascending sequence.

Example 3 — Too Small Array

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

› Output: false

💡 Note: Array too small (length 4 < 7). Need at least 7 elements for valid triplet positions.

Constraints

7 ≤ nums.length ≤ 2000
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with 7+ elements to be divided

Find Dividers

Search for valid triplet (i, j, k)

Check Equality

Verify all four parts have equal sum

Key Takeaway

🎯 Key Insight: Fix the middle divider to reduce from 3D to 2D matching problem

Asked in

G Google 25 f Facebook 18 M Microsoft 12

The key insight is to fix the middle divider j and solve two independent matching problems. The hash map approach with prefix sums achieves O(n²) time complexity by avoiding redundant calculations. Best approach: Hash Map with Fixed Middle. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Triplets	O(n⁴)	O(1)	Try every possible triplet (i, j, k) and calculate the four subarray sums
Hash Map with Fixed Middle	O(n²)	O(n)	Fix the middle divider j and use hash map to find matching i and k pairs
Prefix Sum Optimization	O(n³)	O(n)	Precompute prefix sums to calculate subarray sums in O(1) time

Brute Force - Try All Triplets — Algorithm Steps

Iterate through all valid positions for i (1 to n-4)
For each i, iterate through all valid positions for j (i+2 to n-3)
For each j, iterate through all valid positions for k (j+2 to n-2)
Calculate sums of four subarrays and check equality

Visualization

Tap to expand

Step-by-Step Walkthrough

Try i=1

Place first divider at position 1

Try j=3

Place second divider at position 3 (i+2)

Try k=5

Place third divider at position 5 (j+2)

Calculate Sums

Sum each of the four parts and compare

Code -

solution.c — C

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

bool solution(int* nums, int n) {
    if (n < 7) return false;
    
    for (int i = 1; i < n - 5; i++) {
        for (int j = i + 2; j < n - 3; j++) {
            for (int k = j + 2; k < n - 1; k++) {
                int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
                
                for (int x = 0; x < i; x++) sum1 += nums[x];
                for (int x = i + 1; x < j; x++) sum2 += nums[x];
                for (int x = j + 1; x < k; x++) sum3 += nums[x];
                for (int x = k + 1; x < n; x++) sum4 += nums[x];
                
                if (sum1 == sum2 && sum2 == sum3 && sum3 == sum4) {
                    return true;
                }
            }
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Three nested loops O(n³) with O(n) sum calculation for each iteration

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

34.5K Views

Medium Frequency

~25 min Avg. Time

892 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 - Try All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler