Equilibrium point in an Array

The equilibrium point in an array is a position such that the sum of elements on its left is equal to the sum of elements on its right. Given a 1-indexed array of integers, the task is to find the first equilibrium point in the array. If no such point exists, return -1.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [1, 3, 5, 2, 2]
Output: 3
Explanation: At index 3, the sum of elements on the left (1 + 3 = 4) is equal to the sum of elements on the right (2 + 2 = 4).

Example 2:
Input:
arr = [1, 2, 3]
Output: -1
Explanation: No position has equal sum on both sides.

Example 3:
Input:
arr = [1]
Output: 1
Explanation: The only element is the equilibrium point as there are no elements on either side.

Approach to find the equilibrium point in an array

  1. Calculate Total Sum:
    • Start by calculating the total sum of the array elements. This will be used to determine the right sum dynamically as we iterate through the array.
  2. Iterate and Track Left Sum:
    • Initialize left_sum to zero and iterate through each element of the array.
    • For each element at index i, calculate the right_sum as total_sum - left_sum - arr[i].
    • If left_sum is equal to right_sum, the current index is the equilibrium point.
    • Update left_sum by adding the current element to it for the next iteration.
  3. Algorithm:
    • Calculate the total sum of all elements in the array.
    • Traverse each element and keep track of the left sum. If at any index the left sum is equal to the right sum, return that index.
    • If no equilibrium index is found by the end of the loop, return -1.
  4. Complexity Considerations:
    • The solution has a time complexity of O(n) since we iterate through the array twice (once to calculate the total sum and once to find the equilibrium).
    • The space complexity is O(1), as we are using only a constant amount of extra space.

C++ Program to find the equilibrium point in an array

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find the equilibrium point in the array
int equilibriumPoint(vector<int>& arr) {
    int total_sum = 0, left_sum = 0;
    int n = arr.size();

    // Calculate the total sum of the array
    for (int num : arr) {
        total_sum += num;
    }

    // Traverse the array and find the equilibrium point
    for (int i = 0; i < n; i++) {
        int right_sum = total_sum - left_sum - arr[i];
        if (left_sum == right_sum) {
            return i + 1; // Convert to 1-indexed
        }
        left_sum += arr[i];
    }

    return -1; // No equilibrium point found
}

int main() {
    vector<int> arr = {1, 3, 5, 2, 2};
    int result = equilibriumPoint(arr);

    if (result != -1) {
        cout << "Equilibrium point is at index: " << result << endl;
    } else {
        cout << "No equilibrium point found." << endl;
    }

    return 0;
}

Java Program to find the equilibrium point in an array

java
public class EquilibriumPoint {

    // Function to find the equilibrium point in the array
    public static int findEquilibriumPoint(int[] arr) {
        int totalSum = 0, leftSum = 0;
        int n = arr.length;

        // Calculate the total sum of the array
        for (int num : arr) {
            totalSum += num;
        }

        // Traverse the array and find the equilibrium point
        for (int i = 0; i < n; i++) {
            int rightSum = totalSum - leftSum - arr[i];
            if (leftSum == rightSum) {
                return i + 1; // Convert to 1-indexed
            }
            leftSum += arr[i];
        }

        return -1; // No equilibrium point found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 2, 2};
        int result = findEquilibriumPoint(arr);

        if (result != -1) {
            System.out.println("Equilibrium point is at index: " + result);
        } else {
            System.out.println("No equilibrium point found.");
        }
    }
}

Python Program to find the equilibrium point in an array

python
# Function to find the equilibrium point in the array
def find_equilibrium_point(arr):
    total_sum = sum(arr)
    left_sum = 0

    # Traverse the array and find the equilibrium point
    for i, num in enumerate(arr):
        right_sum = total_sum - left_sum - num
        if left_sum == right_sum:
            return i + 1  # Convert to 1-indexed
        left_sum += num

    return -1  # No equilibrium point found

# Example usage
if __name__ == "__main__":
    arr = [1, 3, 5, 2, 2]
    result = find_equilibrium_point(arr)

    if result != -1:
        print("Equilibrium point is at index:", result)
    else:
        print("No equilibrium point found.")

Time Complexity:

  • O(n): We traverse the array twice (once to calculate the total sum and once to find the equilibrium point).

Space Complexity:

  • O(1): We only use a constant amount of additional space for variables

DSA

8611

298

Related Articles