Hackerrank's Sherlock and Array

Question

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<Integer, Integer> 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 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 < N; i++) {
            int NN = s.nextInt();
            int[] arr = new int[NN];
            for(int j = 0; j < 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?

Answer 1

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

        for (int i = index -  1; i > -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;
}

Answer 2

This what my code looks like. If the array is length 1, I put it in an if statement, else the whole array needs to be traversed, saving some time.

Another important thing I have done is that while taking all the input, I have calculated the sum of them, as I am left traversing, then the sum of the array is actually rightSum (rightSum = sum - value of current index).

While I am traversing the left one increased value by adding previous index and right one decreases by the current index value.

 // TODO code application logic here
    Scanner lab = new Scanner(System.in);
    int leftSum = 0;
    int rightSum = 0;
    int testCases = lab.nextInt();
    for (int i = 0; i < testCases; i++) {
        int length = lab.nextInt();
        int temp[] = new int[length];

        for (int j = 0; j < length; j++) {
            temp[j] = lab.nextInt();
            rightSum += temp[j];
        }
        if (length == 1) {
            System.out.println("YES");
        } else {

            rightSum = rightSum - temp[0];
            for (int j = 1; j < length; j++) {
                if (j == length - 1) {
                    System.out.println("NO");
                    break;
                }
                rightSum = rightSum - temp[j];
                leftSum = leftSum + temp[j - 1];
                if (leftSum == rightSum) {
                    System.out.println("YES");
                    break;
                }
            }
        }
        rightSum = 0;
        leftSum = 0;

    }

Answer 3

I have reviewed your code and found you are using two nested loops which are having O(n^2) complexity. There are multiple approaches to solve this problem but I will explain to you the most efficient way to solve this problem and can be easily done in O(n) time using one for loop.

Below are steps which will help you to do the same in O(n) time-

You can drive an equation by using a little bit of mathematics.

Assume we have an array which is the random array {3,7,5,10,2,7,4,2} so, in that, that element exists such that the sum of the left side of all the elements is equal to the sum of the right side all the elements.

I am assuming that element is represented by y and it exists in between somewhere. so some of the left sides of the element is represented by x as I said the sum of all the elements towards the left side is equal to the sum of all the elements towards the right side of that element. so right side sum also can be represented by x. So by seeing this, we can easily say the sum of all elements presents inside the array should be equal to x + y + x.

x + y + x = sum of all the elements

2 x + y=sum of all the elements

2 x = sum of all the elements - y ---> eq 1

if we have x and y such that this equation holds true. It means, there is one element exist correct because in this equation we have to unknowns x and y. so we have to first get the value of x and y and then will place both the values inside the equation and see whether LHS is equals to RHS or not? LHS equals to RHS it means there is some element exist inside the array where the sum of all the elements towards the left side of the element is equal to the right side of the element. Let’s take one example array.

{3,7,5,10,2,7,4,2}

first, I will calculate the sum of all elements.

sum of all the elements= 3+7+5+10+2+7+4+2 sum of all the elements= 40

replace this in eq 1 then you will get below eq

2x =40 - y --> eq 2

as we are not aware of the y but y that's for sure y will belong to any one of the elements which are present inside the array. so will take one element at a time from the array and replace y with that element like that x also. we will take the x value based on y whatever it comes and replace in this question and see whether LHS equals to RHS or not. if we found any such pair of x and y where LHS equals to RHS. It means, we have that element inside the array which holds this criterion true and we will return YES.

for first iteration- {3,7,5,10,2,7,4,2}

y=3, x=0

just replace both values in eq 2 and you can seed

0 is not equal to 37

now move the pointer ahead try this time

y=7, x=0+3=3

just replace both values in eq 2 and you can seed

6 is not equal to 33

....so do the same until you find that element y which satisfy this condition.

now skipping next iterating with y=5 and trying for y=10 know

if y=10 ,x=3+7+5=15

just replace both values in eq 2 and you can seed

30 is equal to 30. It means this the element(y) which we are looking for and where the left sum is equal to the right sum.

Here is the code which passes 100% test case.

static String balancedSums(List<Integer> arr) {
        int x = 0;
        int sum = 0;
        for (int a : arr) {
            sum += a;
        }

        for (int y : arr) {
            if (2 * x == sum - y) {
                return "YES";
            }
            x = x + y;
        }
        return "NO";

    }

Still having doubt you can check out the video tutorial here.

Answer 4

Your performance problem is that you are redoing the same computations over and over again. You keep recomputing the running sums at the extremities. You should have a more intelligent algorithm that caches the running sums from both directions, or precomputes them. Those questions are very often about dynamic programming.

I was confused by the function name isEven (I was thinking even/odd); I think isEqual is better.

I don't get why isEven has the function arguments leftSum and rightSum. Since they are always set to 0, they should just be variables within the method initialized to 0.