See the original problem on HackerRank.
Warning: HackerRank has recently changed the constraints of this problem but it did not update the challenge itself. Now they allow zeros to be part of the input. In particular this can cause empty subarrays to be a valid solution.
For example this was not valid input before the update:


Now it is. A solution is the position 0
since the left subarray is empty.
In the rest of this post we’ll discuss how to fix some snippets which have not automatically accommodated such a new requirement.
Solutions
This challenge can be solved in many ways. This problem is also known as “Equilibrium index of an array”, because we have to find an index that makes the array “balanced”.
Inefficient solution \(O(N^2)\)
For completeness, if we run a loop for each element of the array and we calculate left and right sum for every iteration, we find a solution but at a very high cost.
Let’s explore alternatives.
Linear solutions with no extra space
We can come up with similar approaches to solve this problem linearly and without allocating extra space.
One idea is to get total sum of array first (one scan). Then Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get right sum by subtracting the elements one by one:


This solution does not suffer zeros in the input.
Some variants of this solution based on precalculating the total sum exist. One, for example, consists in running both leftSum and rightSum until they cross or the length of the array is reached.
An alternative clever solution that is worth sharing avoids iterating on the array to calculate the total sum first, resulting in a single scan (by Roberto Melis and Gianluca Maini). It uses a variation of the two pointer technique that we have seen several times in the past Coding Gym labs:


The solution above might not work with zeros in the inuput. For example, for this test it returns “NO”:


C# by Matteo Furlan


C by Michele Liberi


This variation of the two pointer solution works by checking if an element is between two equalsum halves:


Clearly, this solution is particularly good because it runs in a single scan. However, there is some state shared through all the iterations. This makes parallelization a bit more complicated.
Read on for alternatives.
Linear solution with prefix sum
This class of solutions employ an additional array storing the prefix sum of the elements. Actually, since the data are not really needed, we can allocate only the prefix sum array. In a more realistic environment, this decision could be not feasible.
The prefix sum is the incremental sum of all the elements:
\(pre[i] = A[0] + A[1] + … + A[i]\)
Then \(pre[i]\) stores the sum of all the elements from \(0\) to \(i\).
The prefix sum exhibits an interesting property:
\(sum(A[l]A[r]) = pre[r]  pre[l1]\)
That is: the sum of the elements of \(A\) from index \(l\) to index \(r\) is \(pre[r]  pref[l1]\). For instance:


The sum of \(arr\) from index \(1\) to index \(3\) is \(9\), or \(pre[3]  pre[0] = 10  1\).
We also know that the total sum of the elements is \(pre[n1]\).
Traversing over \(i\), we can easily check whether left sum is equal to the right sum this way:
\(pre[i] == pre[n1]  pre[i1]\)
Basically, at each step we verify if \(i1\) is the pivot index.


C++ has the wonderful adjacent_find
to express what we are doing in the for loop more easily:


The two previous solutions suffer zeros in the input with:


To fix it, just add a fake 0
at the beginning of the array  to emulate an “empty subarray”:


And:


Python


Haskell


Another version of this approach, just for fun, consists in using two prefix sums  left and right, and finding the element in common at the same index:


mismatch
runs a linear loop over i
and returns the first occurrence of !pred(left[i], right[i]
. In our case pred
is not_equal_to<>
, so !pred
is like equal_to
. It’s a bit muddled, isn’t it?!
This solution does not suffer zeros in the input.
Why you should care about prefix sum solutions
Prefix sums have a huge advantage compared to the other solutions. They can be very easily parallelized because the resulting algorithm is completely “stateless” (iterations have no interdependencies).
In C++17 we could simply add tag as first parameter of our standard algorithms to enable parallel execution. For instance:


Clearly, balance this with the number of elements you have or the algorhtm will result in worse performance.