Equilibrium Point

Time: O(n)

Space: O(1)

Problem Overview

An equilibrium point is where the sum of elements to the left equals the sum to the right.

Intuition

An equilibrium point is where the sum of elements to the left equals the sum to the right. Compute total sum first. Then traverse left to right: subtract current element from right sum after checking equality.

Algorithm

1total = sum(arr). leftSum = 0.
2For each index i: total -= arr[i] (now total = rightSum).
3If leftSum == total: return i+1 (1-indexed).
4leftSum += arr[i].
5Return −1.

Example Walkthrough

Input: arr = [-7,1,5,2,-4,3,0]

1. total=0. leftSum=0. i=0: total=7≠leftSum. i=1: total=6≠-7. ... i=3: total=-1,leftSum=-1 ✓. Return 4.

Output: 4

Common Pitfalls

• Subtract the current element from rightSum BEFORE comparing (the current element belongs to neither side).

Equilibrium Point.java

Java

// Approach: Compute total sum, then iterate: if leftSum == totalSum - leftSum - arr[i], return i.
// Time: O(n) Space: O(1)
class Solution {
    // Function to find equilibrium point in the array.
    public static int findEquilibrium(int arr[]) {
        int n = arr.length;
        int rightSum = 0;
        for (int i = 0; i < n; i++)
            rightSum += arr[i];

        int count = 0;
        int leftSum = 0;
        for (int i = 0; i < n; i++) {
            rightSum -= arr[i];
            if (i == 0 && leftSum == rightSum)
                return i;
            // int add=rightSum-arr[i-1];
            if (i == 0)
                continue;
            leftSum += arr[i - 1];
            if (leftSum == rightSum)
                return i;

        }
        return -1;
    }
}

/*  
Version 2 - Given two strings s1 and s2. Return the minimum number of operations required to convert s1 to s2.
The possible operations are permitted:

Insert a character at any position of the string.
Remove any character from the string.
Replace any character from the string with any other character.
*/
class Solution {
    public int editDistance(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n][m];
        for (int[] d : dp)
            Arrays.fill(d, -1);

        return func(n - 1, m - 1, s1, s2, dp);
    }

    int func(int i, int j, String s1, String s2, int[][] dp) {
        if (i < 0)
            return j + 1;

        if (j < 0)
            return i + 1;

        if (dp[i][j] != -1)
            return dp[i][j];

        if (s1.charAt(i) == s2.charAt(j))
            return func(i - 1, j - 1, s1, s2, dp);

        return dp[i][j] = 1 + Math.min(func(i, j - 1, s1, s2, dp),
                Math.min(func(i - 1, j, s1, s2, dp), func(i - 1, j - 1, s1, s2, dp)));
    }
}

Was this solution helpful?