The trick is to know that although rows and columns are sorted,overall matrix isn't. That's what i think they were looking for because even i couldn't give them the exact logic but was able to identify the catch and provide a general logic of how I would approach it. They did hire me ;)