Find if array can be divided into two subarrays of equal sum if any one element can be deleted

user_15415729 0
Viewed 794

Given a array of numbers find if there is a way to delete/remove a number from the array and make one partition in the array( dividing the array into two subarrays ) such that sum of elements in subarray1 is equal to sum of elements in subarray2.

A subarray is a contiguous part of array.
Array [1, 2, 3, 4] has (1), (1,2), (2,3,4),(1,2,3,4) etc.. as its subarrays but not (1,3) , (2,4) , (1,3,4), etc..

Now let us consider one example:-

(Follow 0-based indexing )
Array[] = [ 6, 2, 2, 1, 3 ]

Possible solutions
Delete Array[0] => updated array: - [ 2,2,1,3 ]
Possible partition              : - [2,2] and [3,1] where (2+2) = (3+1) = 4
or
Delete Array[1] => updated array: - [ 6,2,1,3 ]
Possible partition              : - [6] and [2,1,3] where (6) = (2+1+3) = 6
or
Delete Array[2] => updated array: - [ 6,2,1,3 ]
Possible partition              : - [6] and [2,1,3] where (6) = (2+1+3) = 6

Now a similar question already exists where we just have to, find if array can be divided into two subarrays of equal sum , can be done in O(n) =>

PsuedoCode:- The efficient solution involves calculating sum of all elements of the array in advance. Then for each element of the array, we can calculate its right sum in O(1) time by using total sum of the array elements minus sum of elements found so far. The time complexity of this solution would be O(n) and auxiliary space used by it will be O(1).

So to solve our problem one brute force method is:- remove every element once and check if the array can be divided into two subarrays of equal sum. Thus it will require O(n^2) time.

So can we do better than this time complexity?

sub-array arrays algorithm
2 Answers

You can use a map to keep track of the position at which each value in the array occurs. Then, as you move through the array considering each partition point, if the difference between the left and right halves is present in the map, and in the correct half (determined by comparing whether the left-right difference is positive or negative with the position of the value relative to the current partition point) then you have a solution.

Here's some Java code to illustrate:

static boolean splitDelete(int[] a)
{
    Map<Integer, List<Integer>> map = new HashMap<>();
    for(int i=0; i<a.length; i++)
    {
        List<Integer> idx = map.get(a[i]);
        if(idx == null) map.put(a[i], idx = new ArrayList<>());
        idx.add(i);
    }
    
    int sum = 0;
    for(int v : a) sum += v;
            
    int diff = sum;
    for(int i=0; i<a.length-1; i++)
    {
        diff -= 2*a[i];
        if(map.containsKey(Math.abs(diff)))
            for(int j : map.get(Math.abs(diff)))
                if(diff > 0 == j > i) return true;
    }
    
    return false;
}
user_64388190

As RaffleBuffle pointed out, there could be a few scenarios for the deleted element as we traverse different separation points. For example,

a a a a a a a a a a a a a a
<-----X--------->|<------->

a a a a a a a a a a a a a a
<--------------->|<---X--->

One way to solve it with O(n) overall complexity, could be to traverse twice. Each time checking if the difference between the two sums is in a map of values we've been tracking for the side we came from.

Python code:

def f(A):
  values = set()
  total_sum = sum(A)

  # Traverse from left, each part
  # must have at least one element.
  left_sum = A[0]
  right_sum = total_sum - A[0]
  values.add(A[0])

  for i in range(1, len(A) - 1):
    values.add(A[i])
    left_sum += A[i]
    right_sum -= A[i]

    # We have an element in the left part
    # that's the difference between left
    # and right sums.
    if (left_sum - right_sum) in values:
      return True

  # Traverse from right, each part
  # must have at least one element.
  right_sum = A[len(A)-1]
  left_sum = total_sum - A[len(A)-1]
  values.clear()
  values.add(A[len(A)-1])

  for i in range(len(A) - 2, 0, -1):
    values.add(A[i])
    right_sum += A[i]
    left_sum -= A[i]

    # We have an element in the right part
    # that's the difference between right
    # and left sums.
    if (right_sum - left_sum) in values:
      return True

  return False

As = [
  [1, 2, 1, 1, 1], # True
  [1, 1, 1, 2, 1], # True
  [1, 1, 1, 1, 1, 1], # False
  [6, 2, 2, 1, 3]  # True
]

for A in As:
  print("%s\n%s\n\n" % (A, f(A)))
user_20347870
Related