Tag greedy algorithm

Split Array into Three Equal Sum Segments in C: A Comprehensive Tutorial

Given an integer array, the task is to divide it into three non-empty contiguous segments with equal sum. If possible, return the index pair [i, j] such that:

• sum(arr[0..i]) == sum(arr[i+1..j]) == sum(arr[j+1..n-1])

If impossible, return [-1, -1]. This problem tests your understanding of prefix sums, greedy partitioning, and array traversal.

This tutorial provides an in-depth exploration of splitting an array into three equal sum segments in C: naive O(n³) approach, optimized O(n) approach, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is the Problem?

Find two indices i and j (i < j) such that the array is split into three contiguous non-empty segments with equal sums.

Examples:

text

Input: [1, 3, 4, 0, 4] Output: [1, 2] Explanation: Segment 1: arr[0..1] = 1+3 = 4 Segment 2: arr[2..2] = 4 Segment 3: arr[3..4] = 0+4 = 4 Input: [2, 3, 4] Output: [-1, -1] Explanation: No valid split exists. Input: [1, -1, 1, -1, 1, -1, 1, -1] Output: [1, 3] Explanation: Three segments each sum to 0.

Why This Problem Matters

• Prefix sums: Foundation for range-sum problems.
• Greedy partitioning: Teaches optimal substructure.
• Algorithm optimization: O(n³) → O(n) transformation.
• Interview preparation: Common coding interview question.
• Real-world applications: Load balancing, data partitioning, resource allocation.

Key Insight

For three equal segments, the total sum must be divisible by 3. Each segment’s target sum is total / 3. We can find the first two segments greedily by scanning left to right.

Approaches Overview

Syntax & Core Mechanics

Approach 1: Naive — Try All Partitions

Try every pair (i, j) and check if all three segment sums are equal.

c

#include <stdio.h> #include <stdlib.h> long long findSum(const int arr[], int start, int end) { long long sum = 0; for (int i = start; i <= end; i++) { sum += arr[i]; } return sum; } void findSplitNaive(const int arr[], int n, int *out) { out[0] = -1; out[1] = -1; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { long long sum1 = findSum(arr, 0, i); long long sum2 = findSum(arr, i + 1, j); long long sum3 = findSum(arr, j + 1, n - 1); if (sum1 == sum2 && sum2 == sum3) { out[0] = i; out[1] = j; return; } } } } int main(void) { int arr[] = {1, 3, 4, 0, 4}; int n = sizeof(arr) / sizeof(arr[0]); int result[2]; findSplitNaive(arr, n, result); printf("[%d, %d]\n", result[0], result[1]); return 0; }

Expected output:

text

[1, 2]

Time: O(n³), Space: O(1)

Approach 2: Greedy — Find First Two Segments

Steps:

1. Compute total. If total % 3 != 0, return [-1, -1].
2. Set target = total / 3.
3. Scan left to right; accumulate currSum.
4. When currSum == target, record index, reset currSum = 0.
5. When two segments found and there are remaining elements, return the indices.

c

#include <stdio.h> void findSplit(const int arr[], int n, int *out) { out[0] = -1; out[1] = -1; if (n < 3) return; long long total = 0; for (int i = 0; i < n; i++) { total += arr[i]; } if (total % 3 != 0) return; long long target = total / 3; long long currSum = 0; int found = 0; for (int i = 0; i < n; i++) { currSum += arr[i]; if (currSum == target) { currSum = 0; out[found++] = i; if (found == 2 && i < n - 1) { return; } } } /* If we reach here, no valid split */ out[0] = -1; out[1] = -1; } int main(void) { int arr[] = {1, 3, 4, 0, 4}; int n = sizeof(arr) / sizeof(arr[0]); int result[2]; findSplit(arr, n, result); printf("[%d, %d]\n", result[0], result[1]); return 0; }

Expected output:

text

[1, 2]

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

Step-by-Step Trace for [1, 3, 4, 0, 4]

text

total = 12, target = 4 i=0: currSum = 1 i=1: currSum = 4 == target → out[0] = 1, currSum = 0 i=2: currSum = 4 == target → out[1] = 2, found=2, i=2 < 4 → return Result: [1, 2] ✓

Handling All-Zero Segments

If total == 0, target is 0, and any prefix sum equal to 0 triggers segment recording. The algorithm correctly handles this.

text

Input: [1, -1, 1, -1, 1, -1, 1, -1] total = 0, target = 0 i=0: currSum = 1 i=1: currSum = 0 == target → out[0] = 1, currSum = 0 i=2: currSum = 1 i=3: currSum = 0 == target → out[1] = 3, found=2, i=3 < 7 → return Result: [1, 3] ✓

Edge Case: What if Third Segment is Empty?

The condition i < n - 1 ensures at least one element remains for the third segment. Without this check, we might record a second segment at the last index, leaving no elements for the third segment.

Full Practical Code Example with Explanation

This program demonstrates both approaches with verification, performance comparison, and edge cases.

Program: Split Array into Three Equal Sum Segments

c

/** * split_three_equal_segments.c * Finds indices to split array into three equal-sum segments. * Compares naive O(n^3) and greedy O(n) approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ void findSplitNaive(const int arr[], int n, int *out); void findSplitGreedy(const int arr[], int n, int *out); long long findSum(const int arr[], int start, int end); int verifySplit(const int arr[], int n, int i, int j); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Split Array into Three Equal Sum Segments ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; int result[2]; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nArray: "); printArray(arr, n); findSplitGreedy(arr, n, result); printf("Split indices: [%d, %d]\n", result[0], result[1]); if (result[0] != -1) { printf("Segments:\n"); printf(" Segment 1 [0..%d]: sum = %lld\n", result[0], findSum(arr, 0, result[0])); printf(" Segment 2 [%d..%d]: sum = %lld\n", result[0] + 1, result[1], findSum(arr, result[0] + 1, result[1])); printf(" Segment 3 [%d..%d]: sum = %lld\n", result[1] + 1, n - 1, findSum(arr, result[1] + 1, n - 1)); } break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Sum of subarray */ long long findSum(const int arr[], int start, int end) { long long sum = 0; for (int i = start; i <= end; i++) { sum += arr[i]; } return sum; } /* Naive: O(n^3) */ void findSplitNaive(const int arr[], int n, int *out) { out[0] = -1; out[1] = -1; if (n < 3) return; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { long long sum1 = findSum(arr, 0, i); long long sum2 = findSum(arr, i + 1, j); long long sum3 = findSum(arr, j + 1, n - 1); if (sum1 == sum2 && sum2 == sum3) { out[0] = i; out[1] = j; return; } } } } /* Greedy: O(n) */ void findSplitGreedy(const int arr[], int n, int *out) { out[0] = -1; out[1] = -1; if (n < 3) return; long long total = 0; for (int i = 0; i < n; i++) { total += arr[i]; } if (total % 3 != 0) return; long long target = total / 3; long long currSum = 0; int found = 0; for (int i = 0; i < n; i++) { currSum += arr[i]; if (currSum == target) { currSum = 0; out[found++] = i; if (found == 2 && i < n - 1) { return; } } } out[0] = -1; out[1] = -1; } /* Verifies the split */ int verifySplit(const int arr[], int n, int i, int j) { if (i < 0 || j < 0 || i >= j || j >= n - 1) return 0; long long s1 = findSum(arr, 0, i); long long s2 = findSum(arr, i + 1, j); long long s3 = findSum(arr, j + 1, n - 1); return (s1 == s2 && s2 == s3); } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demonstrates both approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {1, 3, 4, 0, 4}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int r1[2]; printf("\nArray 1: "); printArray(arr1, n1); findSplitNaive(arr1, n1, r1); printf(" Naive: [%d, %d]\n", r1[0], r1[1]); if (r1[0] != -1) { printf(" Verification: %s\n", verifySplit(arr1, n1, r1[0], r1[1]) ? "PASS" : "FAIL"); } findSplitGreedy(arr1, n1, r1); printf(" Greedy: [%d, %d]\n", r1[0], r1[1]); if (r1[0] != -1) { printf(" Verification: %s\n", verifySplit(arr1, n1, r1[0], r1[1]) ? "PASS" : "FAIL"); } int arr2[] = {2, 3, 4}; int n2 = sizeof(arr2) / sizeof(arr2[0]); int r2[2]; printf("\nArray 2: "); printArray(arr2, n2); findSplitGreedy(arr2, n2, r2); printf(" Greedy: [%d, %d] (impossible)\n", r2[0], r2[1]); int arr3[] = {1, -1, 1, -1, 1, -1, 1, -1}; int n3 = sizeof(arr3) / sizeof(arr3[0]); int r3[2]; printf("\nArray 3: "); printArray(arr3, n3); findSplitGreedy(arr3, n3, r3); printf(" Greedy: [%d, %d]\n", r3[0], r3[1]); if (r3[0] != -1) { printf(" Verification: %s\n", verifySplit(arr3, n3, r3[0], r3[1]) ? "PASS" : "FAIL"); } int arr4[] = {1, 1, 1, 1, 1, 1}; int n4 = sizeof(arr4) / sizeof(arr4[0]); int r4[2]; printf("\nArray 4: "); printArray(arr4, n4); findSplitGreedy(arr4, n4, r4); printf(" Greedy: [%d, %d]\n", r4[0], r4[1]); if (r4[0] != -1) { printf(" Verification: %s\n", verifySplit(arr4, n4, r4[0], r4[1]) ? "PASS" : "FAIL"); } } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison ===\n"); /* Naive only feasible for small arrays */ int smallN = 100; int *smallArr = malloc(smallN * sizeof(int)); if (smallArr == NULL) return; for (int i = 0; i < smallN; i++) { smallArr[i] = 1; } clock_t start, end; double timeTaken; int result[2]; start = clock(); findSplitNaive(smallArr, smallN, result); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d): Result = [%d, %d], Time = %.3f ms\n", smallN, result[0], result[1], timeTaken); free(smallArr); /* Large array for greedy */ int largeN = 99999; /* Divisible by 3 */ int *largeArr = malloc(largeN * sizeof(int)); if (largeArr == NULL) return; for (int i = 0; i < largeN; i++) { largeArr[i] = 3; } start = clock(); findSplitGreedy(largeArr, largeN, result); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Greedy (n=%d): Result = [%d, %d], Time = %.3f ms\n", largeN, result[0], result[1], timeTaken); printf("\nVerification: %s\n", verifySplit(largeArr, largeN, result[0], result[1]) ? "PASS" : "FAIL"); free(largeArr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); int result[2]; /* Case 1: Empty array */ int arr1[] = {}; printf("Case 1: Empty array\n"); findSplitGreedy(arr1, 0, result); printf(" Result: [%d, %d]\n", result[0], result[1]); /* Case 2: Single element */ int arr2[] = {5}; printf("\nCase 2: Single element\n"); findSplitGreedy(arr2, 1, result); printf(" Result: [%d, %d]\n", result[0], result[1]); /* Case 3: Two elements */ int arr3[] = {1, 2}; printf("\nCase 3: Two elements\n"); findSplitGreedy(arr3, 2, result); printf(" Result: [%d, %d]\n", result[0], result[1]); /* Case 4: Exactly 3 elements, sum divisible by 3 */ int arr4[] = {1, 1, 1}; printf("\nCase 4: Exactly 3 elements\n"); printf(" Array: "); printArray(arr4, 3); findSplitGreedy(arr4, 3, result); printf(" Result: [%d, %d]\n", result[0], result[1]); /* Case 5: Sum not divisible by 3 */ int arr5[] = {1, 2, 3, 4}; printf("\nCase 5: Sum not divisible by 3\n"); printf(" Array: "); printArray(arr5, 4); findSplitGreedy(arr5, 4, result); printf(" Result: [%d, %d]\n", result[0], result[1]); /* Case 6: All zeros */ int arr6[] = {0, 0, 0, 0, 0, 0}; printf("\nCase 6: All zeros\n"); printf(" Array: "); printArray(arr6, 6); findSplitGreedy(arr6, 6, result); printf(" Result: [%d, %d]\n", result[0], result[1]); /* Case 7: Negative values */ int arr7[] = {-1, 2, -1, 2, -1, 2}; printf("\nCase 7: Negative values\n"); printf(" Array: "); printArray(arr7, 6); findSplitGreedy(arr7, 6, result); printf(" Result: [%d, %d]\n", result[0], result[1]); if (result[0] != -1) { printf(" Verification: %s\n", verifySplit(arr7, 6, result[0], result[1]) ? "PASS" : "FAIL"); } /* Case 8: Third segment empty (invalid) */ int arr8[] = {1, 1, 1, 0}; printf("\nCase 8: Potential empty third segment\n"); printf(" Array: "); printArray(arr8, 4); findSplitGreedy(arr8, 4, result); printf(" Result: [%d, %d]\n", result[0], result[1]); /* Case 9: Large values (overflow check) */ int arr9[] = {1000000000, 1000000000, 1000000000}; printf("\nCase 9: Large values\n"); printf(" Array: "); printArray(arr9, 3); findSplitGreedy(arr9, 3, result); printf(" Result: [%d, %d] (long long protects from overflow)\n", result[0], result[1]); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Naive: Tries all (i, j) pairs; O(n³).
2. Greedy: Finds first two segments equal to total/3; O(n).
3. Key check: total % 3 == 0 and i < n - 1 for the second segment.

Expected Output (sample run)

text

=== Split Array into Three Equal Sum Segments === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [1, 3, 4, 0, 4] Naive: [1, 2] Verification: PASS Greedy: [1, 2] Verification: PASS Array 2: [2, 3, 4] Greedy: [-1, -1] (impossible) Array 3: [1, -1, 1, -1, 1, -1, 1, -1] Greedy: [1, 3] Verification: PASS Array 4: [1, 1, 1, 1, 1, 1] Greedy: [1, 3] Verification: PASS --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Empty array Result: [-1, -1] Case 2: Single element Result: [-1, -1] Case 3: Two elements Result: [-1, -1] Case 4: Exactly 3 elements Array: [1, 1, 1] Result: [0, 1] Case 5: Sum not divisible by 3 Array: [1, 2, 3, 4] Result: [-1, -1] Case 6: All zeros Array: [0, 0, 0, 0, 0, 0] Result: [1, 3] Case 7: Negative values Array: [-1, 2, -1, 2, -1, 2] Result: [1, 3] Verification: PASS Case 8: Potential empty third segment Array: [1, 1, 1, 0] Result: [-1, -1] Case 9: Large values Array: [1000000000, 1000000000, 1000000000] Result: [0, 1] (long long protects from overflow)

Common Pitfalls, Edge Cases & Memory Considerations

1. Sum Not Divisible by 3

If total % 3 != 0, immediately return [-1, -1].

c

if (total % 3 != 0) return;

2. Integer Overflow

Total sum can exceed int for large arrays.

c

long long total = 0; /* Use long long */

3. Empty Third Segment

Ensure at least one element remains for the third segment.

c

if (found == 2 && i < n - 1) { return; /* Third segment has at least one element */ }

4. Array Size Less Than 3

No valid split possible.

c

if (n < 3) return;

5. All-Zero Array

When total == 0, target is 0. Works correctly with the algorithm.

c

int arr[] = {0, 0, 0, 0, 0, 0}; /* Returns [1, 3] */

6. Negative Values

Negative values work correctly; sum can be negative or zero.

7. Overlapping Segments

Segments must be non-overlapping and contiguous.

c

Segment 1: arr[0..i] Segment 2: arr[i+1..j] Segment 3: arr[j+1..n-1]

8. Resetting currSum Correctly

Reset currSum = 0 after finding each valid segment.

c

if (currSum == target) { currSum = 0; out[found++] = i; }

9. Return Value on Failure

Always set out[0] = out[1] = -1 on failure.

c

out[0] = -1; out[1] = -1;

10. Memory Considerations

• Naive: O(1) extra space.
• Greedy: O(1) extra space — preferred.
• Use long long for sums to prevent overflow.
• No dynamic allocation required.

Summary & Best Practices

Splitting an array into three equal sum segments is elegantly solved by the greedy approach in O(n) time and O(1) space. The key insight is that the total sum must be divisible by 3, and we only need to find the first two segments.

Key Takeaways

• Total sum must be divisible by 3.
• Target segment sum = total / 3.
• Scan left to right, accumulating currSum.
• Record index when currSum == target; reset currSum = 0.
• Ensure third segment has at least one element (i < n - 1).
• Naive: O(n³); Greedy: O(n).

Best Practices

1. Use the greedy approach for O(n) time and O(1) space.
2. Check total % 3 == 0 early.
3. Use long long for sums to prevent overflow.
4. Ensure third segment is non-empty with i < n - 1.
5. Handle edge cases: empty, single element, two elements, all zeros.
6. Verify with naive approach during testing.
7. Document segment boundaries in comments.
8. Test with negative values and zeros.
9. Return [-1, -1] on failure.
10. Profile for large arrays.

By mastering this problem, you’ll understand greedy partitioning and prefix-sum techniques, applicable to many array and range problems.