PROBLEM:WRITE A PROGRAM TO FIND THE SADDLE POINT OF A MATRIX, IF IT EXISTS
Program
#include <stdio.h>
#define M 3
#define N 3
int findMin( int a[][N], int row )
{
/* * find min value in row of a. * return the value. */
int min = a[row][0];
int j;
for( j=1; j<N; ++j )
if( a[row][j] < min )
min = a[row][j];
return min;
}
int findMax( int a[][N], int col )
{
/* * find max val in col of a. * return the value. */
int max = a[0][col];
int i;
for( i=1; i<M; ++i )
if( a[i][col] > max )
max = a[i][col];
return max;
}
void saddle( int a[][N] )
{
/* * finds ALL saddle points of a if exist. */
int i, j;
for( i=0; i<M; ++i )
{
int min = findMin( a, i );
for( j=0; j<N; ++j )
{
int max;
max = findMax( a, j );
if( min == max )
printf( "Saddle : (%d,%d).\n", i, j );
}
}
}
int main()
{
int a[M][N] = {5,7,3,7,7,9,7,1,2};
int row, col;
saddle(a);
return 0;
}
Explanation
An M × N matrix is said to have a saddle point if some entry a[i][j] is the smallest in row i and the largest in column j. In the following example matrix, 7 is the saddle point.
| 1 2 3 | a = | 4 5 6 | | 7 8 9 |
The program is simple and could be completed in O(M × N × M) time by using nested for loops. The algorithm is as follows:
for i=0 to M-1 { min = minimum value in row i. // findMin(). for j=0 to N-1 { max = maximum value in column j. // findMax(). if (min == max) print "saddle found at row ", i, "and column ", j. } }
Finding the minimum in a row is O(N) and finding the maximum in a column is O(M). Thus the complexity of the algorithm becomes O(M*(N+N*M)), or O(M*N*M).
Points to Remember
A saddle point is the value which is minimum in the row and maximum in the column.
There can be more than one saddle point in a matrix.
There may be no saddle point in a matrix.
The complexity of the algorithm is O(M × M × N), where M × N is the size of the matrix.
