Hackerrank's Sherlock and Array

Challenge can be found here


Problem Statement


Watson gives Sherlock an array A of length N. Then he
asks him to 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. Formally, find an i, such
that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.


Input Format: The first line contains T, the number of test cases. For
each test case, the first line contains N, the number of elements in
the array A. The second line for each test case contains N
space-separated integers, denoting the array A.


Output Format: For each test case print YES 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; otherwise print NO.


Constraints:


\$1 \le T \le 10\$

\$1 \le N \le 10^5\$

\$1 \le Ai \le 2×10^4\$

\$1 \le i \le N\$

I'm having timeout issues on 2 of the test cases

I have tried two different approaches. Both is of \$O(n^2)\$

First was a recursive approach:

public static boolean isEven(int[] arr, int index, int leftSum, int rightSum) {
        int i = index-1;
        int j = index+1;

        while(i > -1) {
            leftSum += arr[i--];
        }

        while(j < arr.length) {
            rightSum += arr[j++];
        }
        return (leftSum == rightSum) ? true : (index == arr.length-1) ? false : isEven(arr, index+1, 0, 0);
    }

Other one was with the use of Navigable map:

public static boolean isEven(NavigableMap map) {
       int left = 0;
       int right = 0;
       int n = map.size();
       while(n-- > 0) {
           left = right = 0;
           for(Integer i : map.tailMap(n+1).values())  right += i; 
           for(Integer j : map.headMap(n).values()) left += j;
           if (left == right) return true;
       }
       return false;
   }

Here i

Your first example looks much nicer, so I'll focus on that.

First, let's remove the tail recursion in the most obvious way possible:

public static boolean isEven(int[] arr, int index, int leftSum, int rightSum) {
    while (true) {
        int i = index-1;
        int j = index+1;

        while(i > -1) {
            leftSum += arr[i--];
        }

        while(j < arr.length) {
            rightSum += arr[j++];
        }

        if (leftSum == rightSum) {
            return true;
        }
        if (index == arr.length-1) {
            return false
        }

        index += 1;
        leftSum = 0;
        rightSum = 0;
    }
}

Now let's clean it up:

public static boolean isEven(int[] arr) {
    for (int index = 0; index  -1; i--) {
            leftSum += arr[i];
        }

        int rightSum = 0;
        for (int i = index+1; i < arr.length; i++) {
            rightSum += arr[i];
        }

        if (leftSum == rightSum) {
            return true;
        }
    }

    return false;
}

We can combine the sum variables:

public static boolean isEven(int[] arr) {
    for (int index = 0; index  -1; i--) {
            difference += arr[i];
        }
        for (int i = index+1; i < arr.length; i++) {
            difference -= arr[i];
        }

        if (difference == 0) {
            return true;
        }
    }

    return false;
}

Now consider that we don't need to recalculate difference each time. If one iteration we have

|-A-| * |--B--|
1 2 3 4 5 6 7 8

The next we have

|-A-|++ --|-B--|
1 2 3 4 5 6 7 8

Namely, we add 4 to A and subtract 5 from B, which means we add 4 and 5 to the difference. We should also check for empty arrays.

public static boolean isEven(int[] arr) {
    if (arr.length == 0) {
        // Alternatively, return false since there
        // is no element that satisfies the condition.
        throw new IllegalArgumentException();
    }

    int difference = arr[0] - Arrays.stream(arr).sum();
    if (difference == 0) {
        return true;
    }

    for (int i = 1; i < arr.length; i++) {
        difference += arr[i-1];
        difference += arr[i];

        if (difference == 0) {
            return true;
        }
    }

    return false;
}

StackExchange Code Review Q#93602, answer score: 7