array of ppl In a rectangular array of people, which will be taller, the tallest of the shortest people in each column, or the shortest of the tallest people in each row? let's see who gets this one w/o using pen & paper. shailesh kumar Friday, March 15, 2002 The shortest of the tallest people. In the worst case, they will be the same. G. Friday, March 15, 2002 I agree.  (Just did it in my head.) Paul Brinkley Friday, March 15, 2002 It's been a couple of days.  Would one of you guys like to elaborate why this is so? Paul Tuesday, March 19, 2002 I derived a proof that shows it will be the tallest of the shortest people. John Edwards Tuesday, March 19, 2002 Okay , so here goes.. Ans : The shortest of the tallest ppl in each row is taller. Proof: Let the tallest of the shortest ppl in each column ( let's call him B ) be in column j. Let the shortest of the tallest ppl in each row ( let's call him A) be in row i .  Consider the man standing at array[i][j] ie row = i and col = j ( call him C ) . Being in row i , C is shorter than A  because A is the tallest in row i. Being in column j , C is taller than B  because B is the shortest in column j. This gives  B < C < A . So A is taller than B. shailesh kumar Wednesday, March 20, 2002   Fog Creek Home