C 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 C, you can find it by checking each element with if it is the row minimum and column maximum using nested loops.

Examples

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

OutputNo saddle point found

InputMatrix: [[3, 1, 3], [3, 2, 4], [0, 2, 3]]

OutputSaddle point is 2 at position (1,1)

InputMatrix: [[10, 20], [5, 15]]

OutputSaddle point is 10 at position (0,0)

How to Think About It

To find a saddle point, look at each element in the matrix. For each element, check if it is the smallest in its row by comparing it with all other elements in the same row. Then check if it is the largest in its column by comparing it with all other elements in the same column. If both conditions are true, that element is a saddle point.

Algorithm

1

Get the matrix input and its size.

2

For each element in the matrix, find the minimum element in its row.

3

Check if this minimum element is also the maximum in its column.

4

If yes, print the element and its position as the saddle point.

5

If no saddle point is found after checking all elements, print no saddle point found.

Code

c

#include <stdio.h>

int main() {
    int matrix[10][10], rows, cols;
    int i, j, k, min, saddle = 0, colIndex;

    printf("Enter number of rows and columns: ");
    scanf("%d %d", &rows, &cols);

    printf("Enter matrix elements:\n");
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    for (i = 0; i < rows; i++) {
        min = matrix[i][0];
        colIndex = 0;
        for (j = 1; j < cols; j++) {
            if (matrix[i][j] < min) {
                min = matrix[i][j];
                colIndex = j;
            }
        }

        int max = min;
        for (k = 0; k < rows; k++) {
            if (matrix[k][colIndex] > max) {
                max = matrix[k][colIndex];
            }
        }

        if (min == max) {
            printf("Saddle point is %d at position (%d,%d)\n", min, i, colIndex);
            saddle = 1;
            break;
        }
    }

    if (!saddle) {
        printf("No saddle point found\n");
    }

    return 0;
}

Output

Enter number of rows and columns: 3 3
Enter matrix elements:
3 1 3
3 2 4
0 2 3
Saddle point is 2 at position (1,1)

Dry Run

Let's trace the example matrix [[3, 1, 3], [3, 2, 4], [0, 2, 3]] through the code

1

Find minimum in row 0

Row 0 elements: 3, 1, 3; minimum is 1 at column 1

2

Check if minimum is max in column 1

Column 1 elements: 1, 2, 2; max is 2, so 1 is not max

3

Find minimum in row 1

Row 1 elements: 3, 2, 4; minimum is 2 at column 1

4

Check if minimum is max in column 1

Column 1 elements: 1, 2, 2; max is 2, so 2 is max

5

Saddle point found

Element 2 at (1,1) is saddle point

Row	Min Element	Column	Max in Column	Saddle Point?
0	1	1	2	No
1	2	1	2	Yes

Why This Works

Step 1: Find row minimum

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

Step 2: Check column maximum

We then check if this minimum element is the largest in its column, which confirms the saddle point condition.

Step 3: Print result

If both conditions are true, we print the saddle point and stop; otherwise, we continue checking other rows.

Alternative Approaches

Check all elements directly

c

#include <stdio.h>

int main() {
    int matrix[10][10], rows, cols;
    int i, j, k, saddle = 0;

    printf("Enter number of rows and columns: ");
    scanf("%d %d", &rows, &cols);

    printf("Enter matrix elements:\n");
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            int val = matrix[i][j];
            int rowMin = 1, colMax = 1;

            for (k = 0; k < cols; k++) {
                if (matrix[i][k] < val) {
                    rowMin = 0;
                    break;
                }
            }

            for (k = 0; k < rows; k++) {
                if (matrix[k][j] > val) {
                    colMax = 0;
                    break;
                }
            }

            if (rowMin && colMax) {
                printf("Saddle point is %d at position (%d,%d)\n", val, i, j);
                saddle = 1;
                break;
            }
        }
        if (saddle) break;
    }

    if (!saddle) printf("No saddle point found\n");
    return 0;
}

This method checks every element directly but is less efficient because it checks all elements in row and column for each element.

Using separate arrays for row mins and column maxes

c

#include <stdio.h>

int main() {
    int matrix[10][10], rows, cols;
    int rowMin[10], colMax[10];
    int i, j, saddle = 0;

    printf("Enter number of rows and columns: ");
    scanf("%d %d", &rows, &cols);

    printf("Enter matrix elements:\n");
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

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

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

    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                printf("Saddle point is %d at position (%d,%d)\n", matrix[i][j], i, j);
                saddle = 1;
                break;
            }
        }
        if (saddle) break;
    }

    if (!saddle) printf("No saddle point found\n");
    return 0;
}

This approach precomputes row minimums and column maximums for faster checks but uses extra memory.

Complexity: O(rows * cols * (rows + cols)) time, O(1) space

Time Complexity

The program uses nested loops to check each element's row and column, leading to O(rows * cols * (rows + cols)) time complexity.

Space Complexity

The program uses only a few extra variables, so space complexity is O(1), working in-place on the input matrix.

Which Approach is Fastest?

Precomputing row minimums and column maximums reduces repeated checks, improving speed at the cost of extra space.

Approach	Time	Space	Best For
Row min + col max check per element	O(rows * cols * (rows + cols))	O(1)	Simple and low memory
Check all elements directly	O(rows * cols * (rows + cols))	O(1)	Straightforward but slower
Precompute row mins and col maxes	O(rows * cols)	O(rows + cols)	Faster with extra memory