Tape Equilibrium O(n)

Question

Problem (Tape Equilibrium):

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])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7 
P = 2, difference = |4 − 9| = 5 
P = 3, difference = |6 − 7| = 1 
P = 4, difference = |10 − 3| = 7 

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.

My solution to it is:

class Solution {
    public int solution(int[] A) {
        long minDiff = Integer.MAX_VALUE;
        long[] leftSums = new long[A.length];
        long totalSum = 0;

        //init
        totalSum += A[0];
        leftSums[0] += 0;  //whatever, don't use leftSums[0] anyway

        for (int i = 1; i < A.length; ++i) {
            totalSum += A[i];
            leftSums[i] += leftSums[i-1] + A[i-1];
        }

        for (int i = 1; i < A.length; ++i) {
            long diff = Math.abs(totalSum - 2 * leftSums[i]);
            if(diff < minDiff){
                minDiff = diff;
            }
        }

        return (int) minDiff;
    }
}

Answer 1

Correctness

I assume this is a toy problem and you don't need to worry about overflow/underflow? If you do, you should be using longs to do all your math, and either returning a long or casting back to an int before you return it.

Performance

You don't need to keep an array of all the left sums. You can get away with just two ints, one containing the sum of numbers on the left and the other containing the sum of numbers on the right. In your second loop, look at the ith element. Add it to the leftSum and subtract it from the rightSum. Use that to do your math.

General

This also cleans up the math you're doing. totalSum - 2 * leftSums[i] is not at all intuitive. Using Math.abs is nice. Using Math.min() would be even nicer.

Java variables start with lowercase letters. int[] A doesn't conform to that standard. Also, abbreviations should be avoided in variable names. minDiff would be better as minimumDifference, and diff would be better as difference.

If I were to code this, it would look something like:

public final class Summer {

    public int solve(final int[] values) {

        long leftSum = 0;
        long rightSum = 0;
        for (int i = 0; i < values.length; i++) {
            rightSum += values[i];
        }

        long minDifference = Integer.MAX_VALUE;
        for (int i = 0; i < values.length; i++) {
            leftSum += values[i];
            rightSum -= values[i];
            final long difference = Math.abs(leftSum - rightSum);
            minDifference = Math.min(minDifference, difference);
        }

        return (int) minDifference;
    }
}

Answer 2

Your algorithm seems efficient time-wise, but it is wasteful of space. As a minor point, it also constrains the input space a little more than necessary (totalSum - 2 * leftSums[i] requires that no prefix of A have a sum larger than Long.MAX_VALUE / 2 or smaller than Long.MIN_VALUE / 2, whereas a different formulation extends those limits such that no prefix (or suffix) can have a sum larger than Long.MAX_VALUE or smaller than Long.MIN_VALUE).

Try this:

class Solution {
    public int solution(int A[]) {
        // currentDiff is right - left for the current partition.
        // Initially, we partition at P = 1.
        long currentDiff = -A[0];

        for (int i = 1; i < A.length; i++) {
            currentDiff += A[i];
        }

        // Now test each partition. minDiff is the minimum difference
        // found so far.
        long minDiff = Math.abs(currentDiff);
        for (int i = 1; i < A.length - 1; i++) {
          currentDiff -= 2 * A[i];  // A[i] moves from right to left.
          minDiff = Math.min(minDiff, Math.abs(currentDiff));
        }
        return (int) minDiff;
    }
}

This requires only \$O(1)\$ additional memory.

Answer 3

The for-loop solutions miss "succeed fast" the opportunity to stop when the absolute minimum is reached. You're always calculating N differences. This one stops potentially in the middle of the array:

const solution = (A) => {
  const len = A.length;
  if (len === 2) {
    return Math.abs((A[0] - A[1]));
  }
  const reducer = (total, amount) => total + amount;
  let rightSum = 0;
  let leftSum = A.reduce(reducer, 0);
  let minDiff = 100000 * 1000; // worst case. expect to be replaced
  let i = len - 1;
  while(minDiff > 0 && i > 0) {
    const el = A[i];
    leftSum -= el;
    rightSum += el;
    minDiff = Math.min(minDiff, Math.abs(leftSum - rightSum));
    i -= 1;
  }
  return minDiff;
};