Python Program to Find Saddle Point in Matrix

A saddle point in a matrix is an element which is the minimum in its row and maximum in its column; in Python, you can find it by checking each row's minimum element and verifying if it is the maximum in its column using code like for i in range(rows): min_val = min(matrix[i]); col = matrix[i].index(min_val); if all(min_val >= matrix[r][col] for r in range(rows)): print(min_val).

Examples

Input[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

OutputSaddle point is 7 at position (2, 0)

Input[[3, 1, 3], [3, 2, 4], [0, 5, 6]]

OutputSaddle point is 3 at position (0, 0)

Input[[10, 20], [30, 40]]

OutputNo saddle point found

How to Think About It

To find a saddle point, look at each row and find its smallest number. Then check if this number is the biggest in its column. If yes, that number is a saddle point. If no such number exists in any row, then there is no saddle point in the matrix.

Algorithm

1

Get the number of rows and columns in the matrix

2

For each row, find the minimum element and its column index

3

Check if this minimum element is the maximum in its column

4

If yes, return this element and its position as the saddle point

5

If no saddle point is found after checking all rows, return that no saddle point exists

Code

python

def find_saddle_point(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    for i in range(rows):
        min_val = min(matrix[i])
        col_index = matrix[i].index(min_val)
        if all(min_val <= matrix[r][col_index] for r in range(rows)):
            print(f"Saddle point is {min_val} at position ({i}, {col_index})")
            return
    print("No saddle point found")

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
find_saddle_point(matrix)

Output

Saddle point is 7 at position (2, 0)

Dry Run

Let's trace the example matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]] through the code

1

Check row 0

Row 0 is [1, 2, 3]. Minimum value is 1 at column 0. Check column 0 values: [1, 4, 7]. Is 1 <= all these? No, because 4 and 7 are greater.

2

Check row 1

Row 1 is [4, 5, 6]. Minimum value is 4 at column 0. Check column 0 values: [1, 4, 7]. Is 4 <= all these? No, because 7 is greater.

3

Check row 2

Row 2 is [7, 8, 9]. Minimum value is 7 at column 0. Check column 0 values: [1, 4, 7]. Is 7 <= all these? Yes, 7 is less than or equal to 7 and greater than 1 and 4.

4

Saddle point found

7 at position (2, 0) is the saddle point.

Row	Min Value	Column Index	Column Values	Is Min Value Max in Column?
0	1	0	[1, 4, 7]	No
1	4	0	[1, 4, 7]	No
2	7	0	[1, 4, 7]	Yes

Why This Works

Step 1: Find minimum in each row

We first find the smallest number in each row because a saddle point must be the minimum in its row.

Step 2: Check if minimum is maximum in its column

Then we check if this minimum number is the largest in its column, which is the other condition for a saddle point.

Step 3: Return the saddle point

If both conditions are true, we return this number and its position as the saddle point; otherwise, we continue checking.

Alternative Approaches

Check maximum in each column first

python

def find_saddle_point_alt(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    for j in range(cols):
        max_val = max(matrix[i][j] for i in range(rows))
        row_index = next(i for i in range(rows) if matrix[i][j] == max_val)
        if all(max_val >= matrix[row_index][k] for k in range(cols)):
            print(f"Saddle point is {max_val} at position ({row_index}, {j})")
            return
    print("No saddle point found")

This method finds the maximum in each column and checks if it is the minimum in its row; it reverses the approach but achieves the same result.

Use numpy for efficient computation

python

import numpy as np

def find_saddle_point_np(matrix):
    arr = np.array(matrix)
    for i in range(arr.shape[0]):
        min_val = arr[i].min()
        col_index = arr[i].argmin()
        if min_val == arr[:, col_index].max():
            print(f"Saddle point is {min_val} at position ({i}, {col_index})")
            return
    print("No saddle point found")

Using numpy simplifies finding min and max values and can be faster for large matrices but requires the numpy library.

Complexity: O(n*m*n) time, O(1) space

Time Complexity

The program loops through each row (n), finds the minimum (m operations), and then checks the column (n operations), resulting in O(n*m*n) time.

Space Complexity

The program uses only a few variables and no extra data structures proportional to input size, so space complexity is O(1).

Which Approach is Fastest?

Using numpy can speed up min and max operations internally, but for small matrices, the simple nested loops approach is sufficient and clear.

Approach	Time	Space	Best For
Row-wise min then column check	O(n*m*n)	O(1)	Small to medium matrices, clarity
Column-wise max then row check	O(n*m*n)	O(1)	Alternative logic, similar performance
Numpy-based approach	Faster in practice	O(n*m)	Large matrices, performance