Home » Algorithm » Datastructure » Interviews » Matrix » Find a Saddle point in Matrix

Find a Saddle point in Matrix

in , , , - on 13:39:00 - No comments

Find Saddle point in a matrix

Given a matrix of n x n size, Find saddle point of matrix.

What is Saddle point of Matrix?
Element is said to be Saddle point of Matrix if it is both a minimum of its row and a maximum of its column or vice versa.

A matrix may have 1 or 2 saddle points or may not have a saddle point. Lets understand what will be input and expected output with the help of an example.


Algorithm

STEP 1: Traverse the Matrix row by row and for each row, find the minimum element in that row.
               let say you find the minimum element at index j.

STEP 2: Check the maximum element on same column j.

STEP 3: If minimum element in row and maximum element in column j is same then that element is 
               Saddle point of Matrix.
               If minimum element in row and maximum element in column j is not same then that row 
               doesn't has Saddle point and check next row.
              
STEP 4: Repeat above steps for all rows.


Java Program to Print Saddle point of Matrix

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package javabypatel.matrix;
 
public class FindSaddlePointInMatrix {
 
 public static void main(String[] args) {
  new FindSaddlePointInMatrix();
 }
 
 public FindSaddlePointInMatrix() {
  int[][] matrix = {
   {4, 5, 6},
   {7, 18, 9},
   {5, 1, 3}
  };
  printSaddlePoint(matrix);
 }
 
 private void printSaddlePoint(int[][] matrix) {
  for (int i = 0; i < matrix.length; i++) {
   boolean isSadlePointPresentInRow = true;
    
   int minimum = matrix[i][0];
   int colIndexOfRowMinimum = 0;
    
   //Find minimum in row.
   for(int j=1; j< matrix[0].length; j++){
    if(matrix[i][j] < minimum){
     minimum = matrix[i][j];
     colIndexOfRowMinimum = j;
    }
   }
    
   //Find maximum in same column.
   for (int j = 0; j < matrix.length; j++) {
    if(minimum < matrix[j][colIndexOfRowMinimum]){
     isSadlePointPresentInRow = false;
     break;
    }
   }
    
   if(isSadlePointPresentInRow){
    System.out.println(minimum);
   }
  }
 }
  
}

You may also like to see

Compress a given string in-place and with constant extra space.

Check whether a given string is an interleaving of String 1 and String 2.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Serialize and Deserialize a Binary Tree

Advanced Multithreading Interview Questions In Java


Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.
Categories: , , ,