Find an Index of Array Such that Sum of Left and Right Subarray is Equal

This is one of the questions that was asked in the competitive coding round for Morgan Stanley.

Problem statement:

You have given an array (list in case of Python). Find the index of the element in the array such that the sum of all the elements left to the index is equal to the sum of all the elements right to the index.

This question can also be asked as

Split the array into equal sum subarrays.

Example:

Input (given array list):
[2, 4, 5, 1, 2, 3]

Output:
2

Explanation:
The left and right sub array for the index "2" is [2, 4] and [1, 2, 3]. The sum of both the sub array is 6. 

There are multiple ways to find the index of the array such that the sum of the left and right subarray is equal.

Method 1

Algorithm

• Traverse each element in the list.
• Check the sum of left and right sub array.
• If the sum of left and right sub array is same, print the index.

This is not an efficient solution. For traversing each element in the list, it will take O(n) time. And to find the sum of the subarray for each index will take O(n) time. So the total complexity of this algorithm is O(n^2).

When I was solving this question on the HackerRank coding round of Morgan Stanley, some of the test cases were failing as it was taking more time.

Can we solve it in more efficient way or in O(n) time?

Yes, you can.

Method 2

Suppose, given array is [2, 4, 5, 1, 2, 3]

Algorithm

• Traverse the array from the left and calculate the cumulative sum at each element. New array formed: [2, 6, 11, 12, 14, 17] (says array “sum_letf”).
• Here, the last element in the new array is nothing but the sum of the given array.
• Take a sum as the first element in the new array. At each element, subtract the element value from the previously calculated value. New array formed: [17, 15, 11, 6, 5, 3] (says array “sum_right”)
• Now compare the two new arrays and find the first matching element. Here matching element is 11 at the index of 2

Python Program

As the second method is efficient we are going to write a Python program for it.

Prerequisite:

• Python List Tutorial which include iterating over each element in the list and append() new element.

sample = [2, 4, 5, 1, 2, 3]

sum = 0

sum_left=[]
for val in sample:
    sum += val
    sum_left.append(sum)
    
sum_right=[]
for val in sample:
    sum_right.append(sum)
    sum -= val

for i in range(len(sum_left)):
    if sum_left[i] == sum_right[i]:
        print(f"Matching index is {i}.")
        break

Output:

Matching index is 2.

Complexity

To calculate the “sum_left” and “sum_right” array it takes O(n) time each. To find the matching element in the new arrays, it takes O(n) time. The total complexity of this algorithm is O(n)+O(n)+O(n) which is equivalent of O(n).

This is more efficient than the first method considering time complexity.

The only drawback of this implementation is extra space. We have created additional two arrays of size ‘n’.

Is there a scope to improve it?

Yes. Let’s check the next method.

Method 3

In earlier method, we were doing three things (calculating left sum array, calculating right sum array and then finding the matching element) one after another.

We can club all these three operations inside the single while loop.

Java Code

public class SplitArray { 
  static int findPivot(int[] arr) {
    int l=0;
    int r=arr.length-1;
    int lsum=arr[l];
    int rsum=arr[r];

    while(l<r) {
      if(lsum==rsum && l+2==r)
        return l+1;
      if(lsum<rsum)
        lsum+=arr[++l];
      else
        rsum+=arr[--r];
    }

    return -1;	
  }
	
  //main function
  public static void main(String args[]) 
  { 
    int arr[] = {2, 4, 5, 1, 2, 3}; 
    int size = arr.length;
    System.out.println(findPivot(arr)); 
  } 
} 

Output:

2

This code is shared by Harshit Garg.

Python Code

def findPivot(arr):
  l=0
  r=len(arr)-1
  lsum=arr[l]
  rsum=arr[r]

  while l<r:
    if lsum==rsum and l+2==r:
      return l+1
    elif lsum<rsum:
      l += 1
      lsum+=arr[l]
    else:
      r -= 1
      rsum+=arr[r]

  return -1

print(findPivot([2, 4, 5, 1, 2, 3]))

Output:

2

Complexity

This is the most efficient method considering both time and space complexity. The time complexity is O(n). And the space complexity is O(1) (constant time) as don’t require any extra space.

Check other competitive coding questions asked in product-based companies.

Understand the logic here to find the index of array such that sum of left and right subarray is equal. You can implement the same code in any other programming language such as C/C++ and Java.