Program to find the saddle point coordinates in a given matrix | Faceprep

Program to find the saddle point coordinates in a given matrix is discussed here.  A saddle point is an element of the matrix, which is the minimum element in its row and the maximum in its column.

For example, consider the matrix given below

                              1    2     3 

Mat[3][3] =     4     5     6

                               7     8     9

Here, 7 is the saddle point because it is the minimum element in its row and maximum element in its column.

saddle point coordinates in a matrix

Algorithm to to find the saddle point coordinates in a given matrix

  1. Input the matrix from the user.
  2. Use two loops, one for traversing the row and the other for traversing the column.
  3. If the current element is the minimum element in its row and maximum element in its column, then return its coordinates.
  4. Else, continue traversing.

Program to find the saddle point coordinates in a given matrix is given below.

// C program to find the saddle point coordinates in the given matrix

#include <stdio.h>

int main()
{
int i, j, k, m, n, min, max,pos[2][2];

/* Input the size of the matrix from the user */
printf(“Enter the square matrix order : “);
scanf(“%d”, &m);

int matrix[m][m];

/* Input the matrix */
printf(“\nInput the matrix : “);
for (i = 0; i < m; i++)
{
for (j = 0; j < m; j++)
{
scanf(“%d”, &matrix[i][j]);
}
}

printf(“\nThe matrix is \n”);
for (i = 0; i < m; i++)
{
for (j = 0; j < m; j++)
{
printf(“%d “, matrix[i][j]);
}
printf(“\n”);
}

/* find the saddle points in the given matrix */
for (i = 0; i < m; i++)
{
min = matrix[i][0];
for (j = 0; j < m; j++)
{
if (min >= matrix[i][j])
{
min = matrix[i][j];
pos[0][0] = i;
pos[0][1] = j;
}
}

j = pos[0][1];
max = matrix[0][j];
for (k = 0; k < m; k++)
{
if (max <= matrix[k][j])
{
max = matrix[i][j];
pos[1][0] = k;
pos[1][1] = j;
}
}

/* saddle point is the minimum of a row and maximum of the column */
if (min == max) {
if (pos[0][0] == pos[1][0] &&pos[0][1] == pos[1][1])
{
printf(“\nSaddle point (%d, %d) : %d\n”,pos[0][0], pos[0][1], max);
}
}
}
return 0;
}

// C++ program to find the saddle point coordinates in the given matrix

#include <iostream>
using namespace std;

int main()
{
int i, j, k, m, n, min, max,pos[2][2];

/* Input the size of the matrix from the user */
cout <<“Enter the square matrix order : “;
cin >> m;

int matrix[m][m];

/* Input the matrix */
cout <<“\nInput the matrix : “;
for (i = 0; i < m; i++)
{
for (j = 0; j < m; j++)
{
cin >> matrix[i][j];
}
}

cout <<“\nThe matrix is \n”;
for (i = 0; i < m; i++)
{
for (j = 0; j < m; j++)
{
cout << matrix[i][j] << ” ” ;
}
cout << endl;
}

/* find the saddle points in the given matrix */
for (i = 0; i < m; i++)
{
min = matrix[i][0];
for (j = 0; j < m; j++)
{
if (min >= matrix[i][j])
{
min = matrix[i][j];
pos[0][0] = i;
pos[0][1] = j;
}
}

j = pos[0][1];
max = matrix[0][j];
for (k = 0; k < m; k++)
{
if (max <= matrix[k][j])
{
max = matrix[i][j];
pos[1][0] = k;
pos[1][1] = j;
}
}

/* saddle point is the minimum of a row and maximum of the column */
if (min == max) {
if (pos[0][0] == pos[1][0] &&pos[0][1] == pos[1][1])
{
cout <<“\nSaddle point ( ” << pos[0][0] << “,” << pos[0][1] << ” ) : ” << max << endl;
}
}
}
return 0;
}

// Java program to find the saddle point coordinates in the given matrix

import java.util.Scanner;

public class Main
{
public static void main(String[] args)
{
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int m = 3,k;
int min = 0;
int max = 0;
int [][]pos = new int[2][2];
System.out.print(“\nThe matrix is \n”);
int i,j;
for (i = 0; i < m; i++)
{
for (j = 0; j < m; j++)
{
System.out.print(matrix[i][j] + ” ” );
}
System.out.println();
}
/* find the saddle points in the given matrix */
for (i = 0; i < m; i++)
{
min = matrix[i][0];
for (j = 0; j < m; j++)
{
if (min >= matrix[i][j])
{
min = matrix[i][j];
pos[0][0] = i;
pos[0][1] = j;
}
}

j = pos[0][1];
max = matrix[0][j];
for (k = 0; k < m; k++)
{
if (max <= matrix[k][j])
{
max = matrix[i][j];
pos[1][0] = k;
pos[1][1] = j;
}
}

/* saddle point is the minimum of a row and maximum of the column */
if (min == max)
{
if (pos[0][0] == pos[1][0] &&pos[0][1] == pos[1][1])
{
System.out.print(“\nSaddle point ( ” + pos[0][0] + “,” + pos[0][1] + ” ) : ” + max + “\n”);
}
}
}

}
}

# Python program to find the saddle point coordinates in a given matrix

from array import *
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
m = 3
min = 0
max = 0
pos = [[0 for x in range(2)] for y in range(2)]
print(“\nThe matrix is \n”)
for i in range(0,m):
for j in range(0,m):
print(matrix[i][j], end = ” “)
print()
# find the saddle points in the given matrix */
for i in range(0,m):
min = matrix[i][0]
for j in range(0,m):
if (min >= matrix[i][j]):
min = matrix[i][j]
pos[0][0] = i
pos[0][1] = j

j = pos[0][1];
max = matrix[0][j];
for k in range(0,m):
if (max <= matrix[k][j]):
max = matrix[i][j]
pos[1][0] = k
pos[1][1] = j

# saddle point is the minimum of a row and maximum of the column
if (min == max):
if (pos[0][0] == pos[1][0] and pos[0][1] == pos[1][1]):
print(“\nSaddle point ( “, pos[0][0] , “,” , pos[0][1] , ” ) : ” , max)

Output:

saddle point coordinates in a given matrix

Time complexity: O(n^2)