Equilibrium Index of an Array

This is a Rosetta Code post.

Story

A popular interview question/assessment is to find the equilibrium index of an array. Generally its to assess the candidates approach to a problem more so than actually solving it.

The equilibrium index of an array is an index where the sum of elements at lower indexes (to the left) is equal to the sum of elements at higher indexes (to the right). Should none of the above hold truth, the array has no equilibrium index.

Task

Given the following zero index array [2,2,4,1,3] consisting of integers write a function that determines the equilibrium index. If an equilibrium index exists, return it. Else return -1.

For this example the its clear that the answer is A[2] as shown below

1
2
3
4
5
A[0] + A[1] = A[2]
2    + 2    = 4

A[3] + A[4] = A[2]
1    + 3    = 4

The step by step calculations shown from a simple to cognitively calculate array [1,2,3,4,5] which has no equilibrium index would be as follows

1
2
3
4
5
6
7
8
1         =  1
5 + 4 + 3 = 12

1 + 2     =  3
5 + 4     =  9

1 + 2 + 3 =  6
5         =  5

Solutions

Pseudocode would be acceptable during an interview question but for an assessment I’d expect to see some code (points for unit tests!)

pseudocode

Simplest approach, probably in-efficient but good enough as a first cut.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
iterate over the collection with a for loop `i=0; i<a.len; i++`
if at the first or last index, continue

iterate from the start of the collection with a for loop `ii=0; ii<i; ii++`
    sum the lower bound index values `lowerValues += a[ii]`
    we use `ii<i` as the current index must not be part of the sum

iterate backwards from the end of the collection with a for loop `iii=a.len-1; iii>i; iii--`
    sum the upper bound index values `upperValues += a[iii]`
    we use `iii>i` as the current index must not be part of the sum

if `lowerValues == upperValues`
    return a[i]
else
    return -1

for

Probably not something we would ship to production but good enough to iterate on and refactor to a better design with unit tests. (we always write unit tests right? :D)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for (int i = 0; i < _array.Length; i++)
{
    if (i == 0 || i == _array.Length - 1)
        continue;

    var lowerValues = 0;
    var upperValues = 0;

    for (int ii = 0; ii < i; ii++)
    {
        lowerValues += _array[ii];
    }

    for (int iii = _array.Length-1; iii > i; iii--)
    {
        upperValues += _array[iii];
    }

    if (lowerValues == upperValues)
        return i;
}

return -1;

foreach

Code solution from rosettacode.org

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static IEnumerable<int> EquilibriumIndices(IEnumerable<int> sequence)
{
    var left = 0;
    var right = sequence.Sum();
    var index = 0;
    foreach (var element in sequence)
    {
        right -= element;
        if (left == right)
        {
            yield return index;
        }
        left += element;
        index++;
    }
}

References