question about saddle point

Question

i have following problem

assume that we have a 9*8 matrix

A matrix is said to have a "saddle point " if some position is the smalles 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 to find to computer location of saddle point

Answer 1

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

Answer 2

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 3

you answered the question yourself:

find the position of the minimum element in each row, find the position of the maximum element in each column,

any position which occurs in both lists is a saddle point

there's room for improvement - but basically, that's it

Answer 4

In a nutshell:

1. Iterate through each row, finding the column number of the smallest value in that row.
2. Iterate through each column, finding the row number of the largest value in that column.
3. Iterate through either rows-mins or column-maxes, checking if the corresponding cell is also the max in the other array.

Here's an implementation in Python:

def find_saddle_points(a):
  """Finds saddle points in a, a 2 dimensional array.

  Args:
    a: A 2 dimensional array in row-major (y, x) order.
  Returns:
    A list of (x, y) location of the saddle points.
  """
  # Holds a (value, column) tuple of the min value and its column for each row.
  row_mins = [min((a[row][col], col) for col in range(len(a[row]))) for row in range(len(a))]
  # Holds a (value, row) tuple of the max value and its row for each column.
  col_maxes = [max((a[row][col], row) for row in range(len(a))) for col in range(len(a[0]))]

  ret = []
  for row, (row_min, col) in enumerate(row_mins):
    if col_maxes[col][1] == row:
      ret.append((row, col))
  return ret