TapeEquilibrium Java Implementation

Question

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of:

|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.

Complexity:

• expected worst-case time complexity is \$\mathcal{O}(N)\$;
• expected worst-case space complexity is \$\mathcal{O}(N)\$, beyond input storage (not counting the storage required for input arguments).

Here is my code..

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TapeEquilibium {

    public static void main(String[] args) {
        int[] a = {3,1,2,4,3};
        System.out.println(solution(a));
    }


    public  static int solution(int[] A){

        long totalSum = 0;

        List<Holder> list = new ArrayList<TapeEquilibium.Holder>();
        for(int i=0;i<A.length;i++){
            totalSum = totalSum + A[i];
        }
        long start = A[0];
        for(int i=1;i<A.length;i++){
            Holder holder = new Holder(i,Math.abs((2*start)-totalSum));
            list.add(holder);
            start = start+A[i];
        }

        Collections.sort(list);

        return (int)(list.get(0).sum); 

    }

    static class Holder implements Comparable<Holder>{

        int p;
        long sum;

        public Holder(int p, long sum){
            this.p = p;
            this.sum = sum;
        }

        public int compareTo(Holder o) {
            if(this == o) return 0;
            else{
                return new Long(this.sum).compareTo(new Long(o.sum));
            }
        }
    }
}

Answer 1

Time complexity

The solution doesn't meet the required \$O(N)\$ complexity. Can you spot why?

Collections.sort(list);

As it stands, the time complexity of your implementation is \$O(N\log N)\$. To get the minimum element of a collection, do you really need to sort all the elements?

Unused values, unnecessary complication

The p field of Holder is not used in the compareTo implementation. In general, it's suspicious when a class implements Comparable but compareTo doesn't use all the fields of the class. In fact this field is not used anywhere in the program. So you can simplify by removing it. And once this field is gone, Holder will have only one field left. A class with a single field in it is highly suspicious. Is it really useful?

With Holder eliminated, the implementation can become much simpler, cleaner and faster.

Answer 2

You don't need to keep all differences in an array to find the minimum afterwards. Just keep a left and right sum and update the minimum difference whenever you find a smaller difference.

Here is a Python/pseudo-code solution for this, from which it should become clear what I mean (unfortunately I don't know any Java :( ).

def solution(A):
     left_sum = 0 
     right_sum = sum(A)
     min_diff = abs(left_sum - right_sum)
     for a in A:
         left_sum += a
         right_sum -= a
         temp_diff = abs(left_sum - right_sum)
         if temp_diff < min_diff:
             min_diff = temp_diff
     return min_diff

This has a time complexity of \$\mathcal{O}(2N)\$, because it needs to go over the array once to get the initial sum and once again to find all differences. It has a space complexity of \$\mathcal{O}(1)\$ (neglecting the input array), in contrast to your \$\mathcal{O}(N)\$ solution.