Saddle Point of a Matrix: C, C++, Java, and Python Programs

A saddle point in an M×N matrix is the element at row i, column j that is the minimum in its row and the maximum in its column.

The term comes from the shape of a saddle surface in mathematics, where the critical point is locally minimal in one direction and locally maximal in another (the same geometry formalised here for discrete matrices). The Wikipedia article on saddle points covers the continuous analogue; this article focuses on the discrete matrix version tested in placement rounds.

Both the definition and the algorithm are straightforward. The challenge placement tests target is recognising that the obvious O(M×N×(M+N)) scan can be reduced to O(M×N) with two auxiliary arrays.

What Is a Saddle Point in a Matrix

Formally, element M[i][j] is a saddle point if and only if:

• M[i][j] is the minimum element in row i (less than or equal to every other element in that row), AND
• M[i][j] is the maximum element in column j (greater than or equal to every other element in that column).

Both conditions must hold at the same position. An element that is the minimum of its row but not the maximum of its column is not a saddle point.

Worked Example: 3×3 Matrix

Consider this matrix:

1  2  3
4  5  6
7  8  9

Work through the conditions step by step:

• Row minimums: row 0 minimum is 1, row 1 minimum is 4, row 2 minimum is 7.
• Column maximums: col 0 maximum is 7, col 1 maximum is 8, col 2 maximum is 9.
• Check element 7 at (row 2, col 0): row 2 minimum is 7 (condition 1 satisfied), col 0 maximum is 7 (condition 2 satisfied).
• Result: element 7 at coordinates (row 2, col 0) is the saddle point.

No other element satisfies both conditions simultaneously. Element 1 at (row 0, col 0) is the row minimum but col 0’s maximum is 7, not 1. Element 9 at (row 2, col 2) is the col maximum but row 2’s minimum is 7, not 9.

Brute-Force Approach

The direct approach checks every element against its entire row and its entire column:

1. For each element M[i][j], scan all N elements in row i to confirm it is the row minimum.
2. If confirmed, scan all M elements in column j to confirm it is the column maximum.
3. If both conditions hold, record the coordinates.

This works correctly. The problem is efficiency. For each of the M×N elements, the algorithm scans N values for the row check and M values for the column check. That gives:

• Time: O(M×N×(M+N))
• Space: O(1)

To illustrate the scale difference:

• 100×100 matrix: brute force makes roughly 2,000,000 comparisons; two-pass makes roughly 30,000.
• 1,000×1,000 matrix: brute force makes roughly 2,000,000,000 comparisons; two-pass makes roughly 3,000,000.

Two-Pass Algorithm

The key insight: row minimums and column maximums can each be precomputed in a single pass, then reused for every element check.

Pass 1: Row Minimums

Traverse the matrix row by row. For row i, find the minimum value and store it in row_min[i]. This scans M×N elements once: O(M×N).

Pass 2: Column Maximums

Traverse the matrix column by column. For column j, find the maximum value and store it in col_max[j]. Another M×N scan: O(M×N).

Pass 3: Element Check

For each element M[i][j], compare it against row_min[i] and col_max[j]. If both match, record the coordinates. Each comparison is O(1), and there are M×N elements: O(M×N).

Total time is O(M×N). The space complexity is O(M+N) for the two auxiliary arrays.

This is exactly the same precompute-then-check pattern used in problems like finding the equilibrium index of an array, where a prefix sum is computed once and reused for every candidate index. Recognising this class of pattern is useful: most placement coding rounds include at least one problem that rewards a linear-pass precomputation over repeated nested scans. See the GeeksforGeeks saddle point reference for further reading.

Programs in C, C++, Java, and Python

All four implementations below use the two-pass method. The logic is identical across languages; only the syntax differs.

C

#include <stdio.h>

#define ROWS 3
#define COLS 3

void findSaddlePoints(int mat[ROWS][COLS], int rows, int cols) {
    int rowMin[ROWS], colMax[COLS];
    int i, j;

    /* Pass 1: row minimums */
    for (i = 0; i < rows; i++) {
        rowMin[i] = mat[i][0];
        for (j = 1; j < cols; j++) {
            if (mat[i][j] < rowMin[i])
                rowMin[i] = mat[i][j];
        }
    }

    /* Pass 2: column maximums */
    for (j = 0; j < cols; j++) {
        colMax[j] = mat[0][j];
        for (i = 1; i < rows; i++) {
            if (mat[i][j] > colMax[j])
                colMax[j] = mat[i][j];
        }
    }

    /* Pass 3: find saddle points */
    int found = 0;
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            if (mat[i][j] == rowMin[i] && mat[i][j] == colMax[j]) {
                printf("Saddle point: %d at (%d, %d)\n", mat[i][j], i, j);
                found = 1;
            }
        }
    }
    if (!found)
        printf("No saddle point found.\n");
}

int main() {
    int mat[ROWS][COLS] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    findSaddlePoints(mat, ROWS, COLS);
    return 0;
}

Output: Saddle point: 7 at (2, 0)

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

void findSaddlePoints(vector<vector<int>>& mat) {
    int rows = mat.size();
    int cols = mat[0].size();
    vector<int> rowMin(rows, INT_MAX);
    vector<int> colMax(cols, INT_MIN);

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (mat[i][j] < rowMin[i])
                rowMin[i] = mat[i][j];

    for (int j = 0; j < cols; j++)
        for (int i = 0; i < rows; i++)
            if (mat[i][j] > colMax[j])
                colMax[j] = mat[i][j];

    bool found = false;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (mat[i][j] == rowMin[i] && mat[i][j] == colMax[j]) {
                cout << "Saddle point: " << mat[i][j]
                     << " at (" << i << ", " << j << ")" << endl;
                found = true;
            }
        }
    }
    if (!found)
        cout << "No saddle point found." << endl;
}

int main() {
    vector<vector<int>> mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    findSaddlePoints(mat);
    return 0;
}

Java

public class SaddlePoint {

    static void findSaddlePoints(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;
        int[] rowMin = new int[rows];
        int[] colMax = new int[cols];

        for (int i = 0; i < rows; i++) {
            rowMin[i] = mat[i][0];
            for (int j = 1; j < cols; j++)
                if (mat[i][j] < rowMin[i])
                    rowMin[i] = mat[i][j];
        }

        for (int j = 0; j < cols; j++) {
            colMax[j] = mat[0][j];
            for (int i = 1; i < rows; i++)
                if (mat[i][j] > colMax[j])
                    colMax[j] = mat[i][j];
        }

        boolean found = false;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == rowMin[i] && mat[i][j] == colMax[j]) {
                    System.out.println(
                        "Saddle point: " + mat[i][j] + " at (" + i + ", " + j + ")"
                    );
                    found = true;
                }
            }
        }
        if (!found)
            System.out.println("No saddle point found.");
    }

    public static void main(String[] args) {
        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        findSaddlePoints(mat);
    }
}

Python

def find_saddle_points(mat):
    rows = len(mat)
    cols = len(mat[0])

    row_min = [min(mat[i]) for i in range(rows)]
    col_max = [max(mat[i][j] for i in range(rows)) for j in range(cols)]

    result = []
    for i in range(rows):
        for j in range(cols):
            if mat[i][j] == row_min[i] and mat[i][j] == col_max[j]:
                result.append((i, j, mat[i][j]))
    return result


mat = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
points = find_saddle_points(mat)
if points:
    for row, col, val in points:
        print(f"Saddle point: {val} at ({row}, {col})")
else:
    print("No saddle point found.")

Output: Saddle point: 7 at (2, 0)

Edge Cases

Three situations are worth testing explicitly before submitting this problem in a placement round.

No Saddle Point

Not every matrix has a saddle point. Consider the matrix with rows [1, 3] and [4, 2]:

• Row minimums: row 0 minimum is 1, row 1 minimum is 2.
• Column maximums: col 0 maximum is 4, col 1 maximum is 3.
• Element 1 is the row 0 minimum but col 0’s maximum is 4, not 1.
• Element 2 is the row 1 minimum but col 1’s maximum is 3, not 2.
• Result: no saddle point exists.

The program must handle this gracefully. Both the C version’s if (!found) guard and the Python version’s empty-list check cover this case.

Multiple Saddle Points

A matrix can have more than one saddle point. Consider the matrix with rows [2, 4] and [2, 4]:

• Row minimums: row 0 minimum is 2, row 1 minimum is 2.
• Column maximums: col 0 maximum is 2, col 1 maximum is 4.
• Element at (row 0, col 0) equals row_min[0] and col_max[0]: saddle point.
• Element at (row 1, col 0) equals row_min[1] and col_max[0]: saddle point.
• Result: two saddle points, both at column 0 with value 2.

The algorithm above reports all saddle points, not just the first one found.

Single-Element Matrix

A 1×1 matrix always has a saddle point: the single element is both the row minimum and the column maximum by definition. The code handles this correctly without any special case.

The same discipline applies to related array traversal problems. For finding symmetric pairs in an array, the same boundary checks matter: empty input, single-element input, and all-equal-element cases are the standard three to verify before submission.

Complexity Summary

Approach	Time	Space
Brute force	O(M×N×(M+N))	O(1)
Two-pass	O(M×N)	O(M+N)

For placement rounds, being able to state both approaches and articulate the trade-off is more useful than memorising only the optimised version.

The row-minimum and column-maximum precomputation in this two-pass method is a direct instance of the aggregate-then-check pattern that recurs throughout numerical computation, from batch normalisation statistics in deep learning to key-query attention score computation in transformer models. TinkerLLM at ₹299 is where placement-track students start building with the language models that put these patterns to work at scale.