Equilibrium Point

Given an array of integers arr[],the task is to find the first equilibrium point in the array.

The equilibrium point in an array is an index (0-based indexing) such that the sum of all elements beforethat index is the same as the sumof elements afterit. Return -1 if no such point exists. 

Examples:

Input: arr[] = [1, 2, 0, 3]
Output: 2
Explanation: The sum of left of index 2 is 1 + 2 = 3 and sum on right of index 2 is 0 + 3 = 3.

Input: arr[] = [1, 1, 1, 1]
Output: -1
Explanation: There is no equilibrium index in the array.

Input: arr[] = [-7, 1, 5, 2, -4, 3, 0]
Output: 3
Explanation: The sum of left of index 3 is -7 + 1 + 5 = -1 and sum on right of index 3 is -4 + 3 + 0 = -1.

Constraints:
3 <= arr.size() <= 10⁶
-10⁹ <= arr[i] <= 10⁹

Approach 01:

class Solution {
public:
    int findEquilibrium(vector<int>& arr) {
        float leftSum = float('-inf');
        float rightSum = float('-inf');
        vector<int> prefixSum(arr.size() + 1, 0);
        int totalSum = accumulate(arr.begin(), arr.end(), 0);

        // Compute prefix sum and check for equilibrium index
        for (int i = 0; i < arr.size(); ++i) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
            if (prefixSum[i - 1] == (totalSum - prefixSum[i])) {
                return i;
            }
        }

        return -1;
    }
};

class Solution:
    def findEquilibrium(self, arr):
        leftSum = float('-inf')
        rightSum = float('-inf')
        prefixSum = [0] * (len(arr) + 1)
        totalSum = sum(arr)

        # Compute prefix sum and check for equilibrium index
        for i, value in enumerate(arr):
            prefixSum[i] = prefixSum[i - 1] + value
            if prefixSum[i - 1] == (totalSum - prefixSum[i]):
                return i

        return -1

Time Complexity:

• Prefix Sum Calculation:

  We calculate the prefix sum in a single pass over the array, which takes \( O(n) \), where \( n \) is the size of the array.

• Total Sum Calculation:

  We use the accumulate function to compute the total sum of the array, which also takes \( O(n) \).

• Checking for Equilibrium:

  We check for equilibrium at each index, which is done in \( O(n) \).

• Overall Time Complexity:

  \( O(n) \).

Space Complexity:

• Prefix Sum Array:

  We use an additional array to store prefix sums, which requires \( O(n) \) space, where \( n \) is the size of the input array.

• Additional Variables:

  We use a constant amount of space for variables such as leftSum, rightSum, and totalSum.

• Overall Space Complexity:

  \( O(n) \).