Given an array of integers, find an equilibrium index. An equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

Edit 2017.07.01 Added three more example input & output. Fixed an off-by-one error in the Ruby implementation.

For example, consider the following array A.

       A: -7  1  5  2 -4  3  0
position: 0 1 2 3 4 5 6

Index 3 is an equilibrium index.

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

Index 6 is also an equilibrium index, because sum of zero elements is zero.

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

Index 7 is not an equilibrium index, because it is not a valid index of array A.

Input. The input file consists of one or more arrays, each on a single line. Each array consists of a sequence of integers, each pair separated by a single space. The input file is terminated by an EOF character. Consider the following example.

-7  1  5  2 -4  3  0
1

1 1
1 0
1 0 -1
0 1 -1
1 -1 0

Output. The output file consists of an output line for each array in the input. Each output line consists of an equilibrium index (if any) or -1 when no equilibrium index exists. For example, the following output corresponds to the previous example input.

3
0
-1
-1
0
-1
0
2

Solution

The proposed solution is O(n).

Just consider each position of a given array, from left to right. Start with a variable l for the left sum set to zero and a variable r for the right sum set to the sum of all elements except the first. Then, as you go from left to right, add the element that becomes part of the left side to l and subtract from r the element that leaves the right side. Return the current index when l and r are equal.

Ruby implementation

#!/usr/bin/env ruby

def equilibrium_index nn
return -1 if nn.length == 0
return 0 if nn.length == 1
ls = 0
rs = nn[1..-1].reduce(0, &:+)
return 0 if rs == 0
nn[1..-1].each_with_index do |n, i|
ls += nn[i]
rs -= n
return i + 1 if ls == rs
end
return -1
end

while true
nn = readline.strip.split(' ').map(&:to_i) rescue break
puts equilibrium_index nn
end

Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments