CODEWITHSUNDEEP
algorithm
user466534
user466534

Reputation:

Location of the saddle point

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.

Upvotes: 5

Views: 6680

Answers (4)

Nick Johnson
Nick Johnson

Reputation: 101149

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

Upvotes: 3

polygenelubricants
polygenelubricants

Reputation: 383866

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.

Upvotes: 4

kdo
kdo

Reputation: 266

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

Upvotes: 0

Unreason
Unreason

Reputation: 12704

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

Upvotes: 3

Related Questions