Find a Saddle point in Matrix

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

---

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.