Finding the Equilibrium Index of an Array

The Problem Description

A zero-indexed array A consisting of N integers is given. An
equilibrium index of this array is any integer P such that 0 <=
P < N and the sum of elements of lower indices is equal to the sum
of elements of higher indices, i.e.,

```A[0] + A[1] + ... + A[P-1] =
A[P+1] + ... + A[N-2] + A[N-1].
```

The sum of zero elements is assumed to be equal to 0.

Write a function that, given a zero-indexed array A consisting of
N integers, returns any of its equilibrium indices. The function
should return -1 if no equilibrium index exists.

• Expected worst-case time complexity is O(N)
• Expected worst-case space complexity is O(N), beyond input storage

(not counting the storage required for input arguments).

The above is taken from the problem description by Codility; they discuss one solution (written in C) here.

Notes on this Implementation

First things first: we’ll avoid the `return -1` “C-ism,” as it’s more natural to return `nil` in Ruby. In fact, Ruby sees -1 as `True`, so returning it will break many common predicates, whereas `nil` won’t.

Experienced programmers will observe that this implementation does not meet the `O(n)` time and space complexity requirements as listed above. Absolute simplicity of implementation is the focus right now, but that may change in a future version.

Finally, notice that this short essay is itself a literate program, implemented using the wonderful Org-mode capabilities which are included with the Emacs text editor.

The Inner Loop

Since most of the program’s work is done inside a single `while` loop, we’ll begin there.

Let A be the Ruby array

```[-7, 1, 5, 2, -4, 3, 0].
```

The equilibrium index of A can be computed by hand, so it’s a good place to start. It’s also our first test case (see below).

We’ve chosen to implement the iteration over A using a `while` loop rather than the more idiomatic `Array#each` method since we need to keep track of our current index into the array.

As we begin the loop, the variable `index` is initialized as the length of the array minus one. This is required because Ruby’s arrays are zero-based, but the value returned by its `Array#length` method is not.

```while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
```

We’ll iterate backwards through the array from the end. At each value of `index`, we’ll split A into two smaller arrays, `left` and `right`. This requires allocating two new arrays in memory, reading the values of the desired “slices” of A, and copying them into `left` and `right`, respectively. This operation provides for an implementation that is simple to visualize and understand, but it’s also the reason why we fail to meet the requirements for `O(n)` space and time complexity. A more efficient implementation would avoid these unnecessary allocation and copying steps, and we might change this program at some point to achieve that.

Visualizing the Iteration

Let’s look at `left` and `right` at each stage of the iteration:

We can see that when we split A at `index`, we always leave a “gap” in between, and it’s this gap which will provide us with the answer we seek: the equilibrium index (provided that the equilibrium index is defined for the given array, that is). At every iteration in the diagram above, we sum the values within `left` and `right` using the `Array#reduce` method. If `left` and `right` are equal, `index` is defined as the equilibrium index, and we `return index`. Otherwise, we’ll end up escaping the loop and returning `nil`.

The `equi` Function

Looking briefly at the entire `equi` function, we can see that it’s just a wrapper for the `while` loop. First we set the value of `index` and `len` as bookkeeping measures. We then enter the `while` loop as described above. If the loop completes without returning a value, the program returns to the next outer context and returns the `nil` value, which lets our caller know that this array doesn’t have an equilibrium index.

```def equi(a)
index = a.length-1
len   = a.length-1
while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
nil
end

```

Test Cases

Over the course of developing the program, a number of test cases have come to mind. We’ll begin with the given array A that we started with.

```def test_random
sample_array = [-7, 1, 5, 2, -4, 3, 0]
expected = equi(sample_array)
assert_equal expected, 3
end

```

Here we’ve defined a trivial `pyramid’ array of values that ascend and descend symmetrically.

```def test_trivial_pyramid
sample_array = [1, 2, 3, 4, 3, 2, 1]
expected = equi(sample_array)
assert_equal expected, 3
end
```

This test checks the case where the first value is equal to the sum of all the rest (save the equilibrium index, of course).

``` def test_biggest_first
sample_array = [99, 0, 66, 32, 1]
expected = equi(sample_array)
assert_equal expected, 1
end
```

Similarly, we check for the case where the last value alone is equal to the sum of `left`.

```def test_biggest_last
sample_array = [66, 32, 1, 0, 99]
expected = equi(sample_array)
assert_equal expected, 3
end
```

We should return `nil` for an array with a single element, since the equilibrium index is not defined in that case.

```def test_single_element
sample_array = [0]
expected = equi(sample_array)
assert_equal expected, nil
end
```

The same is true of an array containing a single `nil`.

```def test_single_nil
sample_array = [nil]
expected = equi(sample_array)
assert_equal expected, nil
end
```

The Complete Program Listing

Finally, we have the complete program listing for the `tangle`‘d file `literate-equi.rb`. Since we’ve included our tests by subclassing the `Test::Unit` class, Ruby will run them for us when we invoke the program. Running `ruby literate-equi.rb` at the command shell should return the following output:

```~/Desktop/Dropbox/current/logicgrimoire \$ ruby literate-equi.rb
Started
......
Finished in 0.002195 seconds.

6 tests, 6 assertions, 0 failures, 0 errors
```

The program itself:

```#!/usr/bin/env ruby

require 'test/unit'

def equi(a)
index = a.length-1
len   = a.length-1
while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
nil
end

class TestEqui < Test::Unit::TestCase
def test_random
sample_array = [-7, 1, 5, 2, -4, 3, 0]
expected = equi(sample_array)
assert_equal expected, 3
end

def test_trivial_pyramid
sample_array = [1, 2, 3, 4, 3, 2, 1]
expected = equi(sample_array)
assert_equal expected, 3
end
def test_biggest_first
sample_array = [99, 0, 66, 32, 1]
expected = equi(sample_array)
assert_equal expected, 1
end
def test_biggest_last
sample_array = [66, 32, 1, 0, 99]
expected = equi(sample_array)
assert_equal expected, 3
end
def test_single_element
sample_array = [0]
expected = equi(sample_array)
assert_equal expected, nil
end
def test_single_nil
sample_array = [nil]
expected = equi(sample_array)
assert_equal expected, nil
end

end
```