Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Dec 12, 2011
Matrix Saddle Points
Source: Algo Muse, CSE, IIT Bombay
Problem: An entry aij in a matrix is called a saddle point if it is strictly greater than all the entries in the ith row and strictly lesser than all entries in the jth column or vice-versa. For example, the matrix shown below has two saddle points.
What is the maximum number of saddle points an nxn matrix can have? Update (December 14, 2011): Due to some reason I do not know of, the problem is not there on the Algo Muse website anymore. :P Solution posted by Panna, Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Prasham Rambhia (Aero IITB Fifth Year Undergraduate Student, To be Morgan Stanley Quant) and Insomniac in comments!