This was one of the hardest problem i implemented ( conceptually was simple ), adhoc solution, corner cases ( i had to rewrite the solution a couple of times ).

Good luck with it.