Tape Equilibrium (A problem in time complexity)

Tape Equilibrium: Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|

Problem

A non-empty 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.

Write a function:

def solution(A)

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

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];

each element of array A is an integer within the range [−1,000..1,000].

Example

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

In this example, the function should return 1

Hint

A naive way to think how to solve this problem is to go through each element from second index to second last index, split the array into two parts: left and right and then compute the sum of both left side and right side to get the absolute difference for this split.

But the way we optimize this code is to do away with the need to compute the sum of left side and right side again and again.

In the a better approach, we change what we store in our left and right variable (viz integers, instead of lists).

This is achieved by maintaining two integer variables as left and right that contain the current value of sum of left and right side.

In each step, we update the values left and right by the amount of element which is changing the side from right to left.

Code

def solution(A):
  left = A[0]
  right = sum(A) - A[0]

  g_diff = abs(left - right)

  for i in range(1, len(A) - 1):
      left = left + A[i]
      right = right - A[i]
      l_diff = abs(left - right)
      if (l_diff < g_diff):
          g_diff = l_diff 
  
  return g_diff  

Complexity

O(n)