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 the 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.
This is not an efficient solution. Traversing each element in the list will take O(n) time. And 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 a more efficient way or in O(n) time?
Yes, you can.
Suppose, the given array is [2, 4, 5, 1, 2, 3]
[2, 6, 11, 12, 14, 17] (says array “sum_letf”).[17, 15, 11, 6, 5, 3] (says array “sum_right”)11 at the index of 2 As the second method is efficient we are going to write a Python program for it.
Prerequisite:
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.
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.
In an earlier method, we were doing three things (calculating the left sum array, calculating the right sum array, and then finding the matching element) one after another.
We can club all these three operations inside the single while loop.
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.
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
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.
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on <b>CSEstack.org</b> portal.