1. Overview
In this tutorial, we’ll first learn the definition of the equilibrium indexes of an array. Subsequently, we’ll write a method to identify and locate them.
2. Presentation of the Problem
Given a zero-indexed array A of size N, index i is an equilibrium index if the sum of the elements of lower indices is equal to the sum of the elements of higher indices. That is to say: A[0] + A[1] + … + A[i-1] = A[i+1] + A[i+2] + … + A[N-1]. In particular, for the first and last index of the array, the sum of the other elements should be 0. For example, let’s consider the array {1, -3, 0, 4, -5, 4, 0, 1, -2, -1}:
- 1 is an equilibrium index because A[0] = 1 and A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] + A[9] = 0 + 4 + (-5) + 4 + 0 + 1 + (-2) + (-1) = 1
- 4 is also an equilibrium index since A[0] + A[1] + A[2] + A[3] = 1 + (-3) + 0 + 4 = 2 and A[5] + A[6] + A[7] + A[8] + A[9] = 4 + 0 + 1 + (-2) + (-1) = 2
- A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] = 1 + (-3) + 0 + 4 + (-5) + 4 + 0 + 1 + (-2) = 0 and there is no element with an index greater than 9, so 9 is an equilibrium index for this array, too
- On the other hand, 5 isn’t an equilibrium index because A[0] + A[1] + A[2] + A[3] + A[4] = 1 + (-3) + 0 + 4 + (-5) = -3, whereas A[6] + A[7] + A[8] + A[9] = 0 + 1 + (-2) + (-1) = -2
3. Algorithm
Let’s think about how to find the equilibrium indexes of an array. The first solution that might come to mind is to iterate over all elements and then compute both sums. However, this would entail an inner iteration on the array elements, which would hurt the performance of our algorithm.
As a result, we’ll preferably start with computing all partial sums of the array. The partial sum at index i is the sum of all the elements of A with indexes lower or equal to i. We can do this in one unique iteration over the initial array. Then, we’ll notice that we can obtain the two sums we need thanks to the partial sums array:
- Find the sum of the lower indices elements at index i-1 of the partial sum array; otherwise, it’s 0 if i=0
- The sum of the higher indexes element is equal to the total sum of the array minus the sum of all array elements until index i, or in mathematical terms: A[i+1] + A[i+2] + … + A[N-1] = A[0] + A[1] + … + A[i-1] + A[i] + A[i+1] + … + A[N-1] – (A[0] + A[1] + … + A[i]). The total sum of the array is the value of the partial sum array at index N-1, and the second sum is the value of the partial sum array at index i
Afterward, we’ll simply iterate over the array and add the elements to the equilibrium index list if both expressions are equal. Hence, the complexity of our algorithm is O(N).
4. Computing Partial Sums
In addition to the partial sums, 0 is the sum of the elements of A before index 0. Besides, 0 is the natural starting point for accumulating the sum. Thus, it looks convenient to add one element at the beginning of our partial sum array with the value 0:
int[] partialSums = new int[array.length + 1];
partialSums[0] = 0;
for (int i=0; i<array.length; i++) {
partialSums[i+1] = partialSums[i] + array[i];
}
In a nutshell, in our implementation, the partial sum array contains the sum A[0] + A[1] + … + A[i] at index i+1. In other words, the ith value of our partial sum array equals the sum of all elements of A with indices lower than i.
5. Listing All Equilibrium Indexes
We can now iterate over our initial array and decide if a given index is an equilibrium:
List<Integer> equilibriumIndexes = new ArrayList<Integer>();
for (int i=0; i<array.length; i++) {
if (partialSums[i] == (partialSums[array.length] - (partialSums[i+1]))) {
equilibriumIndexes.add(i);
}
}
As we can see, we gathered all the items that meet the conditions in our result List.
Let’s look at our method as a whole:
List<Integer> findEquilibriumIndexes(int[] array) {
int[] partialSums = new int[array.length + 1];
partialSums[0] = 0;
for (int i=0; i<array.length; i++) {
partialSums[i+1] = partialSums[i] + array[i];
}
List<Integer> equilibriumIndexes = new ArrayList<Integer>();
for (int i=0; i<array.length; i++) {
if (partialSums[i] == (partialSums[array.length] - (partialSums[i+1]))) {
equilibriumIndexes.add(i);
}
}
return equilibriumIndexes;
}
As we named our class EquilibriumIndexFinder, we can now unit test our method on our example array:
@Test
void givenArrayHasEquilibriumIndexes_whenFindEquilibriumIndexes_thenListAllEquilibriumIndexes() {
int[] array = {1, -3, 0, 4, -5, 4, 0, 1, -2, -1};
assertThat(new EquilibriumIndexFinder().findEquilibriumIndexes(array)).containsExactly(1, 4, 9);
}
We used AssertJ to check that the output List contains the correct indexes: Our method behaves as expected!
6. Conclusion
In this article, we designed and implemented an algorithm to find all the equilibrium indexes of a Java array. The data structure doesn’t have to be an array. It could also be a List or any ordered sequence of integers.
As always, the code is available over on GitHub.
