A good friend pointed me to a nice coding challenge she encountered – finding the Equilibrium Index of an array in** O(n)** time.

After a quick discussion we ended up with 2 solutions, and naturally I had to code them up in F#

## Solution 1

This is the same approach to the one you saw in the O(n) solution I posted the other day for the *Multiply Others* problem.

Here, we’ll create two temporary arrays – one that’s the running sum from the * front*, and the other the running sum from the

*, both are O(n) operations.*

**rear**Once we have both, we can return all the indices where the * front* and

*arrays are equal.*

**rear**(the questions usually only ask for one, but it’s nice to see all of them :-P)

This is a O(n) solution in both time and space.

## Solution 2

A more space efficient, O(1), solution is to:

- do one pass to sum the array (as the sum to the right)
- then starting from the front and iteratively subtract elements from that sum until you find an equilibrium index

for example, given 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 elements), 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 equilibrium 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 equilibrium 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 equilibrium index

So, applying this in F# I ended up with this:

notice that I’m generating the output array via comprehensions, this can look a bit odd to people new to F# so I tend to shy away from it and usually go for * seq { … } |> Seq.toArray* instead.

## Try it Yourself

## Links

- Article on GeekForGeek
- DotNetFiddle snippet
- All my Project Euler solutions in F#
- All my Advent of Code solutions in F#

**Yan Cui**

I’m an **AWS Serverless Hero** and the author of **Production-Ready Serverless**. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.

Further reading

Here is a complete list of all my posts on serverless and AWS Lambda. In the meantime, here are a few of my most popular blog posts.

- Lambda optimization tip – enable HTTP keep-alive
- You are thinking about serverless costs all wrong
- Many faced threats to Serverless security
- We can do better than percentile latencies
- I’m afraid you’re thinking about AWS Lambda cold starts all wrong
- Yubl’s road to Serverless
- AWS Lambda – should you have few monolithic functions or many single-purposed functions?
- AWS Lambda – compare coldstart time with different languages, memory and code sizes
- Guys, we’re doing pagination wrong