A saddle point of a matrix is an element of that matrix which is the minimum element of that row and a maximum element of that column. So, a saddle point is a point where the minimum element of the row and the maximum element of the column is the same.
For example:
Let the matrix be
Step 1:
In this matrix the minimum element of the first row is 1, but, in that column, the maximum element is 7. Therefore, 1 is not the saddle point.
Step 2:
In this matrix the minimum element of the second row is 4, but, in that column, the maximum element is 7. Therefore, 4 is not the saddle point.
Step 3:
In this matrix, the minimum element of the third row is 7, and in that column, the maximum element is also 7. Therefore, 7 is the saddle point.
INPUT: A matrix
OUTPUT: The saddle point of the matrix
PROCESS:
Step 1: [Taking the inputs]
Read m, n [the number of rows and columns of the matrix]
[Taking the elements]
For i=0 to m-1 repeat
For j=0 to n-1 repeat
Read a[i][j]
[End of ‘for’ loop]
[End of ‘for’ loop]
Step 2: [Finding the ‘Saddle Point’]
For i = 0 to n-1 repeat
[find the minimum element of row with its column index]
Set row_min<-a[i][0]
Set ci<-0
For j = 1 to n-1 repeat
if row_min >a[i][j] then
Set row_min <-a[i][j]
Set ci<- j
[End of ‘if’]
[End of ‘for’ loop]
[checking the minimum element is the maximum element of the column or not]
for k = 0 to n-1 repeat
if row_min<a[k][ci] then
break
[End of ‘for’ loop]
[If saddle point is present]
if k = n then
print "The Saddle Point is: row_min”
return
[End of ‘if’]
[End of ‘for’ loop]
[If the Saddle Point not found]
Print "The saddle point is not present"
Step 3: Stop.
TIME COMPLEXITY:
for(i = 0; i < n; i++) --------------- O(n)
{
//find the minimum element of row with its column index
row_min=a[i][0],ci=0; -------- O(1)
for(j = 1; j < n; j++) ------ O(n-1)
{ if (row_min >a[i][j]) ----- O(c1)
{ row_min =a[i][j];
ci= j;
}
}
//checking the minimum element is the maximum element of the column or not
for (k = 0; k < n; k++) ------------ O(n)
{ // Note that col_ind is fixed
if (row_min<a[k][ci]) -------- O(c2)
break; }
// If saddle point is present
if (k == n) ------------------ O(c3)
{ printf("\nThe Saddle Point is: %d" ,row_min);
return;
}
}
// If the Saddle Point not found
printf("\nThe saddle point is not present"); -------- O(1)
Here c1, c2 and c3 are constant so, the time complexity is:
O(n*((n-1)*c1+n*c2+c3)) = O().
Related
Contributed by