Find Saddle Point of a Matrix in Java

In this section, we will understand what is saddle point in a matrix, and how to find the saddle point of a matrix through a Java program.

What is the saddle point in a matrix?

In a matrix, an element is called the saddle point that is the minimum (or smallest) element row-wise and maximum (or largest) element column-wise. The term saddle point is widely used in game theory.

Note that a matrix may have more than one, and may not have saddle points. For example, consider the following matrix.

In the above matrix, 10 and 8 are the lowest in the respective column and highest in the respective row. Hence, the above matrix has two saddle points.

In the following matrix, there is no saddle point exists.

Algorithm

• Traverse each row of the matrix one by one and find the minimum elements from each row.
• Traverse the same column for finding the maximum element in which the minimum element is found.
• If the minimum element in the row and maximum element in the column are the same, the element is the saddle point of the matrix.
• If the minimum element in the row and maximum element in the column are not the same, there does not exist a saddle point.
• Repeat the above steps until we do not get the saddle point.

How to find saddle point?

Consider the following matrix and find the saddle point.

Let's find the saddle point.

Row 0: Minimum in row 0 is 4 (at index 0) and maximum in same column 0 is 7. Both elements are different, so row 0 does not contain any saddle point.

Row 1: Minimum in row 1 is 7 (at index 0) and maximum in same column 0 is 7. Both elements are the same, so 7 is the saddle point of the matrix.

Row 2: Minimum in row 2 is 1 (at index 1) and maximum in same column 1 is 8. Both elements are different, so row 2 does not contain any saddle point.

Java Program to Find the Saddle Point in a Matrix

FindSaddlePoint.java

Output:

Let's see another logic.

MatrixSaddlePoint.java

Output:

The saddle point of the matrix is: 7