Equilibrium Index problem in F#

A good friend point­ed me to a nice cod­ing chal­lenge she encoun­tered — find­ing the Equi­lib­ri­um Index of an array in O(n) time.

After a quick dis­cus­sion we end­ed up with 2 solu­tions, and nat­u­ral­ly I had to code them up in F#

 

Solution 1

This is the same approach to the one you saw in the O(n) solu­tion I post­ed the oth­er day for the Mul­ti­ply Oth­ers prob­lem.

Here, we’ll cre­ate two tem­po­rary arrays — one that’s the run­ning sum from the front, and the oth­er the run­ning sum from the rear, both are O(n) oper­a­tions.

Once we have both, we can return all the indices where the front and rear arrays are equal.

(the ques­tions usu­al­ly only ask for one, but it’s nice to see all of them :-P)

This is a O(n) solu­tion in both time and space.

 

Solution 2

A more space effi­cient, O(1), solu­tion is to:

  • do one pass to sum the array (as the sum to the right)
  • then start­ing from the front and iter­a­tive­ly sub­tract ele­ments from that sum until you find an equi­lib­ri­um index

for exam­ple, giv­en the input array [ -1; 3; -4; 5; 1; -6; 2; 1 ], the sum is 1, so if we start from the front of the array:

  • -1 : sum to the left is 0 (no ele­ments), sum to the right is 1 — -1 = 2, no match
  • 3 : sum to the left is -1, sum to the right is 2 — 3 = -1, match, so index 1 is an equi­lib­ri­um index
  • -4 : sum to the left is -1 + 3 = 2, sum to the right is -1 — -4 = 3, no match
  • 5 : sum to the left is 2 + -4 = -2, sum to the right is 3 — 5 = -2, match, index 3 is also an equi­lib­ri­um index
  • 1 : sum to the left is -2 + 5 = 3, sum to the right is -2 — 1 = -3, no match
  • -6 : sum to the left is 3 + 1 = 4, sum to the right is -3 — -6 = 3, no match
  • 2 : sum to the left is 4 + -6 = -2, sum to the right is 3 — 2 = 1, no match
  • 1 : sum to the left is -2 + 2 = 0, sum to the right is 1 — 1 = 0, match, index 7 is also an equi­lib­ri­um index

So, apply­ing this in F# I end­ed up with this:

notice that I’m gen­er­at­ing the out­put array via com­pre­hen­sions, this can look a bit odd to peo­ple new to F# so I tend to shy away from it and usu­al­ly go for seq { … } |> Seq.toArray instead.

 

Try it Yourself

 

Links