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 &gt; -1) {
            leftSum += arr[i--];
        }

        while(j &lt; 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&lt;Integer, Integer&gt; map) {
       int left = 0;
       int right = 0;
       int n = map.size();
       while(n-- &gt; 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 is how I read the input:

public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        final int N = s.nextInt();

        for(int i = 0; i &lt; N; i++) {
            int NN = s.nextInt();
            int[] arr = new int[NN];
            for(int j = 0; j &lt; NN; j++) {
                arr[j] = s.nextInt();   
            }
            System.out.println(isEven(arr, 0, 0, 0) ? "YES" : "NO");
        }
    }


To avoid an \$O(n^2)\$ solution, I can't check every element in the array, or can 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 &gt; -1) {
            leftSum += arr[i--];
        }

        while(j &lt; 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 &lt; arr.length; index++) {
        int leftSum = 0;
        for (int i = index -  1; i &gt; -1; i--) {
            leftSum += arr[i];
        }

        int rightSum = 0;
        for (int i = index+1; i &lt; 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 &lt; arr.length; index++) {
        int difference = 0;

        for (int i = index -  1; i &gt; -1; i--) {
            difference += arr[i];
        }
        for (int i = index+1; i &lt; 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 &lt; arr.length; i++) {
        difference += arr[i-1];
        difference += arr[i];

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

    return false;
}