Equilibrium Index Of An Array in C

An array's equilibrium index is a fascinating concept in computer science, often appearing in coding challenges and algorithm design.

In this article, you will learn how to define, identify, and efficiently compute the equilibrium index of an array using various programming approaches.

Problem Statement

The problem of finding an equilibrium index involves identifying a specific position in an array where the sum of elements to its left equals the sum of elements to its right. This concept is crucial in scenarios requiring balanced data partitioning or resource allocation, such as workload balancing in distributed systems or optimizing data structures. If an index is at either end of the array, the corresponding missing sum (left for index 0, right for index n-1) is considered zero.

Example

Consider the array A = [-7, 1, 5, 2, -4, 3, 0]. An equilibrium index for this array is 3.

• Left sum (elements before index 3): A[0] + A[1] + A[2] = -7 + 1 + 5 = -1
• Right sum (elements after index 3): A[4] + A[5] + A[6] = -4 + 3 + 0 = -1

Since the left sum equals the right sum, index 3 is an equilibrium index.

 

Background & Knowledge Prerequisites

To understand this article, a basic grasp of the following C programming concepts is essential:

• Arrays: Declaring, initializing, and accessing elements.
• Loops: for loops for iteration.
• Variables: Declaring and manipulating integer variables.
• Functions: Basic understanding of defining and calling functions (though we'll keep examples in main for simplicity for introductory articles).

 

Use Cases or Case Studies

The concept of an equilibrium index, or similar balancing problems, appears in various practical applications:

1. Load Balancing: In distributed computing, identifying a "pivot" server where the sum of tasks processed by servers before it equals the sum of tasks by servers after it, to ensure balanced workload distribution.
2. Financial Analysis: Dividing a transaction ledger into two parts where the net value of transactions up to a certain point equals the net value of subsequent transactions, useful for identifying critical balance points.
3. Game Development: Balancing game levels or resources. For instance, finding a point in a game map where resources on one side are balanced with resources on the other.
4. Signal Processing: Identifying a point in a data stream where the accumulated "energy" or "amplitude" on both sides is equal, useful for segmenting signals.
5. Data Partitioning: Optimizing database sharding or data distribution by finding a split point that balances the data volume on either side.

 

Solution Approaches

1. Brute-Force Approach

This approach involves iterating through each element of the array and, for each element, calculating the sum of elements to its left and the sum of elements to its right. If these two sums are equal, the current index is an equilibrium index.

One-line summary: Iterate through each index, calculate left and right sums for that index, and compare them.

// Brute-Force Equilibrium Index
#include <stdio.h>

int findEquilibriumIndexBruteForce(int arr[], int n) {
    if (n == 0) return -1; // Handle empty array

    for (int i = 0; i < n; i++) {
        long long leftSum = 0;
        long long rightSum = 0;

        // Calculate left sum
        for (int j = 0; j < i; j++) {
            leftSum += arr[j];
        }

        // Calculate right sum
        for (int j = i + 1; j < n; j++) {
            rightSum += arr[j];
        }

        if (leftSum == rightSum) {
            return i; // Found an equilibrium index
        }
    }
    return -1; // No equilibrium index found
}

int main() {
    // Step 1: Define an array
    int arr[] = {-7, 1, 5, 2, -4, 3, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Find the equilibrium index using brute force
    int equilibriumIndex = findEquilibriumIndexBruteForce(arr, n);

    // Step 3: Print the result
    if (equilibriumIndex != -1) {
        printf("Equilibrium index found at position: %d\\n", equilibriumIndex);
    } else {
        printf("No equilibrium index found.\\n");
    }

    // Test with another array
    int arr2[] = {1, 2, 3};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    equilibriumIndex = findEquilibriumIndexBruteForce(arr2, n2);
    if (equilibriumIndex != -1) {
        printf("Equilibrium index for {1, 2, 3} found at position: %d\\n", equilibriumIndex);
    } else {
        printf("No equilibrium index for {1, 2, 3} found.\\n");
    }

    return 0;
}

Run

Sample output:

Equilibrium index found at position: 3
No equilibrium index for {1, 2, 3} found.

 

Stepwise explanation:

1. The findEquilibriumIndexBruteForce function takes an array arr and its size n.
2. It iterates from i = 0 to n-1 (outer loop), considering each i as a potential equilibrium index.
3. Inside the outer loop, leftSum and rightSum are initialized to 0 for each i.
4. An inner loop calculates leftSum by summing elements from arr[0] to arr[i-1].
5. Another inner loop calculates rightSum by summing elements from arr[i+1] to arr[n-1].
6. If leftSum equals rightSum, i is returned as the equilibrium index.
7. If no such index is found after checking all possibilities, the function returns -1.
8. The main function then calls this helper and prints the result.

This approach has a time complexity of O(N^2) due to the nested loops.

 

2. Prefix Sum Approach (Optimized)

This approach significantly improves performance by pre-calculating the total sum of the array once. Then, it iterates through the array a second time, maintaining a leftSum and calculating the rightSum on the fly using the total sum.

One-line summary: Calculate total sum once, then iterate, updating leftSum and deriving rightSum from the total sum.

// Prefix Sum Equilibrium Index
#include <stdio.h>

int findEquilibriumIndexPrefixSum(int arr[], int n) {
    if (n == 0) return -1; // Handle empty array

    long long totalSum = 0;
    // Step 1: Calculate the total sum of the array
    for (int i = 0; i < n; i++) {
        totalSum += arr[i];
    }

    long long leftSum = 0;
    // Step 2: Iterate through the array to find equilibrium index
    for (int i = 0; i < n; i++) {
        // rightSum is totalSum - leftSum - current element
        long long rightSum = totalSum - leftSum - arr[i];

        if (leftSum == rightSum) {
            return i; // Found an equilibrium index
        }
        // Update leftSum for the next iteration
        leftSum += arr[i];
    }
    return -1; // No equilibrium index found
}

int main() {
    // Step 1: Define an array
    int arr[] = {-7, 1, 5, 2, -4, 3, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Find the equilibrium index using prefix sum
    int equilibriumIndex = findEquilibriumIndexPrefixSum(arr, n);

    // Step 3: Print the result
    if (equilibriumIndex != -1) {
        printf("Equilibrium index found at position: %d\\n", equilibriumIndex);
    } else {
        printf("No equilibrium index found.\\n");
    }

    // Test with another array
    int arr2[] = {1, 2, 3};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    equilibriumIndex = findEquilibriumIndexPrefixSum(arr2, n2);
    if (equilibriumIndex != -1) {
        printf("Equilibrium index for {1, 2, 3} found at position: %d\\n", equilibriumIndex);
    } else {
        printf("No equilibrium index for {1, 2, 3} found.\\n");
    }

    // Test with an array where 0 is equilibrium
    int arr3[] = {0, 0, 0};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    equilibriumIndex = findEquilibriumIndexPrefixSum(arr3, n3);
    if (equilibriumIndex != -1) {
        printf("Equilibrium index for {0, 0, 0} found at position: %d\\n", equilibriumIndex);
    } else {
        printf("No equilibrium index for {0, 0, 0} found.\\n");
    }

    return 0;
}

Run

Sample output:

Equilibrium index found at position: 3
No equilibrium index for {1, 2, 3} found.
Equilibrium index for {0, 0, 0} found at position: 0

 

Stepwise explanation:

1. The findEquilibriumIndexPrefixSum function first calculates the totalSum of all elements in the array in a single pass.
2. It then initializes leftSum to 0.
3. It iterates through the array from i = 0 to n-1.
4. In each iteration, rightSum is calculated as totalSum - leftSum - arr[i]. This cleverly avoids a separate loop for rightSum.
5. If leftSum equals rightSum, i is returned as the equilibrium index.
6. Before moving to the next iteration, arr[i] is added to leftSum to prepare for the calculation of the next potential equilibrium index.
7. If no equilibrium index is found, the function returns -1.

This approach has a time complexity of O(N) because it involves only two passes over the array (one for total sum, one for checking indices).

 

Conclusion

Finding the equilibrium index of an array is a classic problem with various applications. While a brute-force approach offers a straightforward solution, its O(N^2) time complexity makes it inefficient for large arrays. The optimized prefix sum approach, on the other hand, provides an elegant and highly efficient O(N) solution by leveraging pre-computed sums. Understanding these different approaches helps in choosing the most suitable algorithm based on performance requirements.

Summary

• Equilibrium Index Definition: An index i where the sum of elements to its left equals the sum of elements to its right. Edge cases (index 0, index n-1) have a corresponding sum of zero.
• Brute-Force Approach:
• Concept: Iterate through each index, and for each, calculate left and right sums using nested loops.
• Time Complexity: O(N^2).
• Suitability: Small arrays or when simplicity is prioritized over performance.
• Prefix Sum Approach:
• Concept: Calculate the total array sum first. Then, iterate once, maintaining a running leftSum and deriving rightSum from totalSum and leftSum.
• Time Complexity: O(N).
• Suitability: Larger arrays or when optimal performance is required.

Quiz / Call to Action

1. Challenge: What would be the equilibrium index for the array [10, 5, -5, 10]? Try to calculate it mentally or by hand before running any code.
2. Coding Task: Modify the findEquilibriumIndexPrefixSum function to return all equilibrium indices if multiple exist, instead of just the first one. How would you store and return these multiple indices?
3. Reflect: When would you absolutely need the O(N) solution over the O(N^2) solution? Think about constraints on array size and available computational resources.