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:

http://logicgrimoire.files.wordpress.com/2012/02/wpid-equi.png?w=630

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 
Loaded suite literate-equi
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

About these ads

2 thoughts on “Finding the Equilibrium Index of an Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s