Here is an O(N) functional solution in C# LINQ: http://pastebin.com/fvdmQBFC

Making the solution "functional" was by far the most time-consuming part of the exercise.