1
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think your program works correctly. For example, if the first or last array element is 0, your program returns true no matter what the other array elements are. \$\endgroup\$ – JS1 Aug 23 '17 at 5:04
  • \$\begingroup\$ @JS1 great catch! I think the solution is that I should only start comparing left/right sums when i >= j. \$\endgroup\$ – Jae Bradley Aug 23 '17 at 5:18
  • \$\begingroup\$ That may fix something but you should test many test cases to be sure your program is correct. In particular, make sure your program can find an answer on both the left and right sides of the array. \$\endgroup\$ – JS1 Aug 23 '17 at 5:46
4
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.