> I regularly see similar problems at work.

No way anyone gets that in 30 minutes without having seen it exactly before. Moving pointers in from the sides, according to Y height, both at the same time when equal, and then not using that to find the solution, just to narrow the search space? I mean, it's not like I and everyone else didn't think along those lines, but that exact algorithm is totally non-obvious. I spent like 20 minutes on something similar, another 20 on a recursive split/merge thing that went nowhere, then got brute force working.