Tag left right sum

Equilibrium Index in C: A Comprehensive Tutorial

The equilibrium index of an array is an index where the sum of all elements to the left equals the sum of all elements to the right. Finding this index is a classic algorithmic problem that tests your understanding of prefix sums, array traversal, and time-space trade-offs.

This tutorial provides an in-depth exploration of finding the equilibrium index in C: naive nested-loop approach, prefix/suffix array approach, optimized running-sum approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is an Equilibrium Index?

An equilibrium index i in an array arr[] of size n satisfies:

text

Sum(arr[0..i-1]) == Sum(arr[i+1..n-1])

Key boundary rules:

• At index 0: Left sum is 0 (empty left side).
• At index n-1: Right sum is 0 (empty right side).

Examples:

text

Input: [1, 2, 0, 3] Output: 2 Explanation: Left of index 2 = 1+2 = 3; Right of index 2 = 3. Equal. Input: [1, 1, 1, 1] Output: -1 Explanation: No equilibrium index. Input: [-7, 1, 5, 2, -4, 3, 0] Output: 3 Explanation: Left of index 3 = -7+1+5 = -1; Right of index 3 = -4+3+0 = -1.

Why This Problem Matters

• Prefix sum technique: Foundation for range-sum problems.
• Optimization: O(n²) → O(n) with O(1) space.
• Interview preparation: Common coding interview question.
• Real-world applications: Load balancing, pivot detection, data partitioning.
• Foundation for advanced problems: Pivot finding, partition algorithms.

Approaches Overview

Approach	Time Complexity	Space Complexity
Naive nested loops	O(n²)	O(1)
Prefix/suffix arrays	O(n)	O(n)
Running sums	O(n)	O(1)

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

For each index, compute left and right sums using inner loops.

c

#include <stdio.h> int findEquilibriumNaive(const int arr[], int n) { for (int i = 0; i < n; i++) { int leftSum = 0; for (int j = 0; j < i; j++) { leftSum += arr[j]; } int rightSum = 0; for (int j = i + 1; j < n; j++) { rightSum += arr[j]; } if (leftSum == rightSum) { return i; } } return -1; } int main(void) { int arr[] = {-7, 1, 5, 2, -4, 3, 0}; int n = sizeof(arr) / sizeof(arr[0]); printf("Equilibrium index: %d\n", findEquilibriumNaive(arr, n)); return 0; }

Expected output:

text

Equilibrium index: 3

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

Approach 2: Prefix and Suffix Arrays

Precompute prefix and suffix sums for O(1) lookup.

c

#include <stdio.h> #include <stdlib.h> int findEquilibriumPrefixSuffix(const int arr[], int n) { if (n <= 0) return -1; int *pref = malloc(n * sizeof(int)); int *suff = malloc(n * sizeof(int)); if (pref == NULL || suff == NULL) { free(pref); free(suff); return -1; } pref[0] = arr[0]; for (int i = 1; i < n; i++) { pref[i] = pref[i - 1] + arr[i]; } suff[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) { suff[i] = suff[i + 1] + arr[i]; } int result = -1; for (int i = 0; i < n; i++) { if (pref[i] == suff[i]) { result = i; break; } } free(pref); free(suff); return result; } int main(void) { int arr[] = {-7, 1, 5, 2, -4, 3, 0}; int n = sizeof(arr) / sizeof(arr[0]); printf("Equilibrium index: %d\n", findEquilibriumPrefixSuffix(arr, n)); return 0; }

Expected output:

text

Equilibrium index: 3

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

Approach 3: Running Prefix and Suffix Sums (Optimal)

Track prefix sum while deriving suffix sum from total.

Key formula:

text

Suffix(i) = Total - Prefix(i) - arr[i]

c

#include <stdio.h> int findEquilibrium(const int arr[], int n) { if (n <= 0) return -1; /* Compute total sum */ long long total = 0; for (int i = 0; i < n; i++) { total += arr[i]; } /* Iterate tracking prefix sum */ long long prefSum = 0; for (int i = 0; i < n; i++) { long long suffSum = total - prefSum - arr[i]; if (prefSum == suffSum) { return i; } prefSum += arr[i]; } return -1; } int main(void) { int arr[] = {-7, 1, 5, 2, -4, 3, 0}; int n = sizeof(arr) / sizeof(arr[0]); printf("Equilibrium index: %d\n", findEquilibrium(arr, n)); return 0; }

Expected output:

text

Equilibrium index: 3

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

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

text

total = -7 + 1 + 5 + 2 + (-4) + 3 + 0 = 0 i=0: prefSum = 0, suffSum = 0 - 0 - (-7) = 7 → 0 ≠ 7 prefSum = -7 i=1: prefSum = -7, suffSum = 0 - (-7) - 1 = 6 → -7 ≠ 6 prefSum = -6 i=2: prefSum = -6, suffSum = 0 - (-6) - 5 = 1 → -6 ≠ 1 prefSum = -1 i=3: prefSum = -1, suffSum = 0 - (-1) - 2 = -1 → -1 == -1 ✓ Return 3

---

Full Practical Code Example with Explanation

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

Program: Equilibrium Index Finder

c

/** * equilibrium_index.c * Finds an equilibrium index where left sum == right sum. * Compares naive, prefix/suffix arrays, and running-sum 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 */ int findEquilibriumNaive(const int arr[], int n); int findEquilibriumPrefixSuffix(const int arr[], int n); int findEquilibriumRunning(const int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void verifyEquilibrium(const int arr[], int n, int idx); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Equilibrium Index Finder ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. 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; 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); int naive = findEquilibriumNaive(arr, n); int prefSuff = findEquilibriumPrefixSuffix(arr, n); int running = findEquilibriumRunning(arr, n); printf("Naive result: %d\n", naive); printf("Prefix/Suffix result: %d\n", prefSuff); printf("Running result: %d\n", running); int consistent = (naive == prefSuff && prefSuff == running); printf("Verification: %s\n", consistent ? "PASS" : "FAIL"); if (running != -1) { verifyEquilibrium(arr, n, running); } 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; } /* Naive: O(n^2) */ int findEquilibriumNaive(const int arr[], int n) { if (n <= 0) return -1; for (int i = 0; i < n; i++) { long long leftSum = 0; for (int j = 0; j < i; j++) { leftSum += arr[j]; } long long rightSum = 0; for (int j = i + 1; j < n; j++) { rightSum += arr[j]; } if (leftSum == rightSum) { return i; } } return -1; } /* Prefix/suffix arrays: O(n) time, O(n) space */ int findEquilibriumPrefixSuffix(const int arr[], int n) { if (n <= 0) return -1; long long *pref = malloc(n * sizeof(long long)); long long *suff = malloc(n * sizeof(long long)); if (pref == NULL || suff == NULL) { free(pref); free(suff); return -1; } pref[0] = arr[0]; for (int i = 1; i < n; i++) { pref[i] = pref[i - 1] + arr[i]; } suff[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) { suff[i] = suff[i + 1] + arr[i]; } int result = -1; for (int i = 0; i < n; i++) { if (pref[i] == suff[i]) { result = i; break; } } free(pref); free(suff); return result; } /* Running sums: O(n) time, O(1) space */ int findEquilibriumRunning(const int arr[], int n) { if (n <= 0) return -1; long long total = 0; for (int i = 0; i < n; i++) { total += arr[i]; } long long prefSum = 0; for (int i = 0; i < n; i++) { long long suffSum = total - prefSum - arr[i]; if (prefSum == suffSum) { return i; } prefSum += arr[i]; } return -1; } /* 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"); } /* Verifies equilibrium index */ void verifyEquilibrium(const int arr[], int n, int idx) { if (idx < 0 || idx >= n) return; long long leftSum = 0, rightSum = 0; for (int i = 0; i < idx; i++) leftSum += arr[i]; for (int i = idx + 1; i < n; i++) rightSum += arr[i]; printf(" Verification at index %d: Left=%lld, Right=%lld → %s\n", idx, leftSum, rightSum, (leftSum == rightSum) ? "VALID" : "INVALID"); } /* Demonstrates all approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {1, 2, 0, 3}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("Naive: %d\n", findEquilibriumNaive(arr1, n1)); printf("Prefix/Suffix: %d\n", findEquilibriumPrefixSuffix(arr1, n1)); printf("Running: %d\n", findEquilibriumRunning(arr1, n1)); int arr2[] = {1, 1, 1, 1}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Running: %d (no equilibrium)\n", findEquilibriumRunning(arr2, n2)); int arr3[] = {-7, 1, 5, 2, -4, 3, 0}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3: "); printArray(arr3, n3); printf("Running: %d\n", findEquilibriumRunning(arr3, n3)); verifyEquilibrium(arr3, n3, findEquilibriumRunning(arr3, n3)); int arr4[] = {1, 7, 3, 6, 5, 6}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4: "); printArray(arr4, n4); printf("Running: %d\n", findEquilibriumRunning(arr4, n4)); verifyEquilibrium(arr4, n4, findEquilibriumRunning(arr4, n4)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 20000) ===\n"); int n = 20000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } srand(42); for (int i = 0; i < n; i++) { arr[i] = (rand() % 200) - 100; } clock_t start, end; double timeTaken; start = clock(); int naiveResult = findEquilibriumNaive(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (O(n^2)): Result = %d, Time = %.3f ms\n", naiveResult, timeTaken); start = clock(); int prefResult = findEquilibriumPrefixSuffix(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Prefix/Suffix (O(n)): Result = %d, Time = %.3f ms\n", prefResult, timeTaken); start = clock(); int runResult = findEquilibriumRunning(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Running (O(n)): Result = %d, Time = %.3f ms\n", runResult, timeTaken); printf("\nVerification: %s\n", (naiveResult == prefResult && prefResult == runResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Single element */ int arr1[] = {5}; printf("Case 1: Single element\n"); printf(" Array: "); printArray(arr1, 1); printf(" Equilibrium: %d (index 0; left=0, right=0)\n", findEquilibriumRunning(arr1, 1)); /* Case 2: Two elements, equal */ int arr2[] = {1, 1}; printf("\nCase 2: Two equal elements\n"); printf(" Array: "); printArray(arr2, 2); printf(" Equilibrium: %d\n", findEquilibriumRunning(arr2, 2)); /* Case 3: Equilibrium at start */ int arr3[] = {0, 1, 2, 3}; printf("\nCase 3: Equilibrium at start (index 0)\n"); printf(" Array: "); printArray(arr3, 4); printf(" Equilibrium: %d (left=0, right=1+2+3=6? No)\n", findEquilibriumRunning(arr3, 4)); /* Case 4: Equilibrium at end */ int arr4[] = {1, 2, 3, 0}; printf("\nCase 4: Equilibrium at end\n"); printf(" Array: "); printArray(arr4, 4); printf(" Equilibrium: %d\n", findEquilibriumRunning(arr4, 4)); /* Case 5: Multiple equilibrium indices (return first) */ int arr5[] = {0, 0, 0, 0}; printf("\nCase 5: Multiple equilibrium indices\n"); printf(" Array: "); printArray(arr5, 4); printf(" Equilibrium (first): %d\n", findEquilibriumRunning(arr5, 4)); /* Case 6: All negative */ int arr6[] = {-1, -2, -3, -2, -1}; printf("\nCase 6: Symmetric negatives\n"); printf(" Array: "); printArray(arr6, 5); printf(" Equilibrium: %d\n", findEquilibriumRunning(arr6, 5)); verifyEquilibrium(arr6, 5, findEquilibriumRunning(arr6, 5)); /* Case 7: Large values (overflow check) */ int arr7[] = {1000000000, 1000000000, -1000000000, 1000000000}; printf("\nCase 7: Large values\n"); printf(" Array: "); printArray(arr7, 4); printf(" Equilibrium: %d (long long protects from overflow)\n", findEquilibriumRunning(arr7, 4)); } /* 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: Nested loops; O(n²) time.
2. Prefix/Suffix Arrays: Precomputes sums; O(n) time, O(n) space.
3. Running Sums: Derives suffix from total; O(n) time, O(1) space.

Expected Output (sample run)

text

=== Equilibrium Index Finder === --- Menu --- 1. Demonstrate All Approaches 2. Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [1, 2, 0, 3] Naive: 2 Prefix/Suffix: 2 Running: 2 Array 2: [1, 1, 1, 1] Running: -1 (no equilibrium) Array 3: [-7, 1, 5, 2, -4, 3, 0] Running: 3 Verification at index 3: Left=-1, Right=-1 → VALID Array 4: [1, 7, 3, 6, 5, 6] Running: 3 Verification at index 3: Left=11, Right=11 → VALID --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Single element Array: [5] Equilibrium: 0 (index 0; left=0, right=0) Case 2: Two equal elements Array: [1, 1] Equilibrium: -1 Case 3: Equilibrium at start (index 0) Array: [0, 1, 2, 3] Equilibrium: 0 (left=0, right=1+2+3=6? No) Case 4: Equilibrium at end Array: [1, 2, 3, 0] Equilibrium: -1 Case 5: Multiple equilibrium indices Array: [0, 0, 0, 0] Equilibrium (first): 0 Case 6: Symmetric negatives Array: [-1, -2, -3, -2, -1] Equilibrium: 2 Verification at index 2: Left=-3, Right=-3 → VALID Case 7: Large values Array: [1000000000, 1000000000, -1000000000, 1000000000] Equilibrium: -1 (long long protects from overflow)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Forgetting to Exclude the Pivot

The suffix sum excludes the pivot element: Suffix(i) = Total - Prefix(i) - arr[i].

2. Integer Overflow

Sum can exceed int for large arrays.

c

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

3. Single Element

Index 0 is always an equilibrium index (left=0, right=0).

c

int arr[] = {5}; /* Equilibrium index = 0 */

4. Empty Array

Return -1 for empty arrays.

c

if (n <= 0) return -1;

5. Multiple Equilibrium Indices

Return the first (leftmost) index.

c

for (int i = 0; i < n; i++) { if (prefSum == suffSum) return i; /* First match */ prefSum += arr[i]; }

6. Off-by-One in Prefix/Suffix

The prefix at i includes arr[i]; the suffix at i includes arr[i]. Comparing pref[i] == suff[i] works because both include the pivot.

7. Negative Values

Negative values work correctly; the algorithm handles them naturally.

8. All Zeros

Every index is an equilibrium; return the first (0).

c

int arr[] = {0, 0, 0, 0}; /* Return 0 */

9. Memory Leaks in Prefix/Suffix

Free dynamically allocated arrays.

c

free(pref); free(suff);

10. Memory Considerations

• Naive: O(1) extra space.
• Prefix/Suffix: O(n) extra space.
• Running: O(1) extra space — preferred.
• Use long long for sums to prevent overflow.

---

Summary & Best Practices

Finding the equilibrium index is elegantly solved with running prefix sums in O(n) time and O(1) space. The key formula is Suffix(i) = Total - Prefix(i) - arr[i].

Key Takeaways

• Equilibrium index: left sum = right sum.
• At index 0: left sum = 0.
• At index n-1: right sum = 0.
• Naive: O(n²) time.
• Prefix/Suffix: O(n) time, O(n) space.
• Running: O(n) time, O(1) space — optimal.
• Return first equilibrium index from left.

Best Practices

1. Use the running-sum approach for O(n) time and O(1) space.
2. Use long long for sums to prevent overflow.
3. Handle edge cases: empty, single element, all zeros.
4. Return the leftmost equilibrium index.
5. Verify with the naive approach during testing.
6. Free prefix/suffix arrays when using that approach.
7. Document the formula in comments.
8. Test with negative values and large arrays.
9. Use size_t for array sizes where appropriate.
10. Profile for large arrays.

By mastering this problem, you’ll understand prefix-sum techniques, which are fundamental to many array and range-query problems.