Location of the saddle point

Question

I have the following problem

Assume that we have a 9*8 matrix

A matrix is said to have a "saddle point", if in some position is the smallest value in its row and the largest value in its column . In symbols , a[i][j] is a saddle point if

 a[i][j]=min a[i][k]  ==max a[k][k]
             1<=k<=8      1<=k<=9

Please help me finding the computer location of the saddle point.

Answer 1

Given MxN matrix, this is O(MN), which is optimal.

INIT rowMin = [ +Infinify ] xM
INIT colMax = [ -Infinity ] xN

FOR r = 1..M
  FOR c = 1..N
    rowMin[r] = MIN(rowMin[r], mat[r][c])
    colMax[c] = MAX(colMax[c], mat[r][c])

FOR r = 1..M
  FOR c = 1..N
    IF mat[r][c] == rowMin[r] == colMax[c]
       DECLARE saddlePoint(r, c)

---

Why is this optimal?

Because there are MxN values, and they each need to be looked at, so for your answer to be certain (i.e. not probabilistic), the lowerbound is O(MN).

Can this be optimized further?

You can optimize this a bit. It'll still be O(MN), but instead of finding the maximum/minimum values, you find their indices instead. This can make the second phase O(M) in the best case (i.e. when there's a unique min/max in a row/column).

Note that in the worst case, there are O(MN) saddle points: that's when the numbers in the array are all equal.

Answer 2

Naive solution is to:

• find smallest values of all rows
• find largest values of columns
• see if any of them are at the same position