Facebook Hacker Cup had a similar problem: https://www.facebook.com/hackercup/problems.php?pid=53250625...

I almost solved it; after screwing around for a while trying to record only one value for each square, I realized you need to store two values for each square. If we’re looking for the upper-left corner we can put a window, each dead pixel/pixel “poisons” all the pixels less than the width of the window to the left of it and the height of the window above it. Then you just do a linear scan over the remaining pixels. I think my problem was that I used too much RAM because I was trying to store the whole 2D grid; you only need to keep one dimension in memory.

You can see people’s submissions here: https://www.facebook.com/hackercup/scoreboard?round=18989011...

This problem is interesting. It doesn't make any sense to use an N^3 solution like the Meebo problem if N can be so large. I haven't looked at any solutions, but it seems like an N*lg N + WH solution would pass.