For an array, check if an index exists where the sum of the elements to the left of it is equal to the sum of the elements right of it

Question

Problem

Extended from this HackerRank problem.

Given an array A of length n, determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero.

For example, [ 1, 1, 1, 2 ], the sum of elements to the left and right of index 2 are equal.

Approach

The following description is for the left-to-right evaluation of the array of values. In my implementation, I do both the left-to-right and right-to-left evaluations in the same loop.

1. Given an array of values, start with the first and last index. These will be the initial values of the left and right sums and the initial left and right indices
2. Increment the left index by 1 and decrement the right index by 1
   1. If the left index is less than the right index, add the value at the right index to the right sum
   2. If the left index is greater than the right index, subtract the value at the left index from the right sum
   3. If the left and right sums are the same, then return early
   4. Else, add the value at the left index to the left sum
3. After exiting the loop, check if the left sum is equal to the right sum

Implementation

public class BalancedArraySumIdentifier {
    public static boolean isBalanced(int[] values) {
        int leftToRightLeftSum = 0;
        int leftToRightRightSum = 0;

        int rightToLeftRightSum = 0;
        int rightToLeftLeftSum = 0;

        for (int i = 0; i < values.length; i++) {
            int j = values.length - 1 - i;

            if (i < j) {
                leftToRightRightSum += values[j];
                rightToLeftLeftSum += values[i];
            } else if (i > j) {
                leftToRightRightSum -= values[i];
                rightToLeftLeftSum -= values[j];
            }

            if (leftToRightLeftSum == leftToRightRightSum || rightToLeftLeftSum == rightToLeftRightSum) {
                return true;
            }

            leftToRightLeftSum += values[i];
            rightToLeftRightSum += values[j];
        }

        return leftToRightLeftSum == leftToRightRightSum || rightToLeftLeftSum == rightToLeftRightSum;
    }
}

Answer 1

First of all, I don't think your final return statement is correct: As far as I can figure, it compares the total sum of the array numbers to 0, which is in no way relevant to the question, and it causes the program to output true for arrays like [-1,1] or [1,2,-3].

Also, as you have already discovered with the help of JS1's observation, leftToRightRightSum and rightToLeftLeftSum only contain valid values once i >= j - 1, or, in other words, once every number in the array has been iterated over by at least one of the two pointers. Likewise, once these two variables contain valid values, the two pointers combined again iterate over every number in the array to check whether one of them fulfills the condition stated in the task.

So your two pointers merely divide the work that could as well be done by one single pointer: Calculate the total sum of the numbers (first array iteration), and then go through the array and divide the total sum into left and right for every element (second array iteration). This might seem like more work because code-wise it requires two iterations whereas your code only requires one iteration, but on the other hand, your code does more work per iteration loop than this algorithm would do due to the presence of two pointer variables, so in the end, I guess that there wouldn't be much difference in performance.

public static boolean isBalanced(int[] values) {
    int totalSum = Arrays.stream(values).sum(); // first "iteration"

    for (int i = 0, leftSum = 0, rightSum = totalSum;
            i < values.length;
            i++) { //second iteration
        rightSum -= values[i];
        if (leftSum == rightSum) {
            return true;
        }
        leftSum += values[i];
    }

    return false;
}

Answer 2

this may require taking every index of the array and check if the sum of left and right are equal, if we think about it the difference between left and right must be 0(left-right==0). so we can take the total sum first and minus the 0 index value to it and check if it equals 0. if not sum the 0 indexes to the left and minus it from the total sum which means the total sum becomes the right sum. next minus the 1 index from total(now it act as a right sum) and check if it is equal to the left sum. if not the array will keep doing this till it's < the array length.

also, you may customize the function to return integer so you could exactly determine which index does return.

public static boolean isBalanced(int[] values){
    int totalSum=0;
    for(int i=0;i<values.length;i++){
        totalSum+=values[i];
    }
    int leftSum=0;
    for(int i=0;i<values.length;i++){
        totalSum-=values[i];
        if(leftSum==totalSum)
        return true;
        leftSum+=values[i];
    }
    return false;
}