Thanks Chris for this solution. I ran it, and it passed all tests!
IMO, the art of interviewing is extracting as much information about the interviewee in that one hour as possible. If it took 3 hrs to write this solution, then it would be very difficult for someone to do it it one hour under pressure and explain the code.
As long as someone has solid programming skills, given a day or two on the real job, they could probably arrive at this optimal solution as well, if it was a business requirement. It's just not reasonable to expect it in an interview.
In 1999, we were building a real time OLAP solution for a Wall St customer. It was a multi-dimensional survey where the Wall St Chief Economist can ask for those who answered D in question 21, how did they answer the other questions, for example.
We were running SQL Server 7 back then, which was the first introduction of OLAP/BI analysis tools. The DBA's original query took almost 10 minutes to return a response. My boss asked me to optimize it for a web page. After a series of "can you make it faster" nudges, I got it down to less than 5 seconds (IIRC), fast enough for a web page response time.
Could I do that in an interview setting? No. I was hired for my Visual Basic skills and had to learn SQL on the job. But given enough time, I could learn a new skill and optimize the heck out of it.
This is why interviewing is hard. Learned knowledge is confused for intelligence and grit.