ISC Practicals and Theory - Saddle Point

A saddle point of a matrix is an element that is the smallest in its row and the largest in its column at the same time. This program, written in the main method alone, reads an $m \times n$ matrix, checks the order, prints the matrix and then prints every saddle point with its position, or NO SADDLE POINT if there is none.

Definition

An element a[i][j] of an $m \times n$ matrix is a saddle point if:

• it is the minimum of row i, and
• it is the maximum of column j.

Some books define a saddle point the other way round (the maximum of its row and the minimum of its column). This note and its program use the minimum of the row and the maximum of the column.

Example: in the matrix with rows 1 2 3, 4 5 6, 7 8 9, the row minima are 1, 4, 7 and the column maxima are 7, 8, 9. The element 7 (row 2, column 0) is the smallest in its row and the largest in its column, so it is the saddle point.

Equal values. An element counts if it is *equal to* the row minimum and *equal to* the column maximum, so repeated values are allowed in the matrix. If two saddle points exist, they must have the same value. For the matrix with rows 3 1 2, 2 0 1, 1 1 4, the value 1 at row 0, column 1 and the value 1 at row 2, column 1 are both saddle points.

A matrix may have no saddle point, for example the rows 3 1 and 2 4.

Algorithm

1. Read the number of rows m and columns n. If either is not from 2 to 10, print Invalid size and stop.
2. Create the array a of order m x n, read the elements row by row and print the matrix.
3. Set count = 0. For every row i, find min, the smallest element of the row: assume a[i][0] is the smallest and compare it with the rest of the row.
4. For every column j of that row, find max, the largest element of column j, in the same way down the column.
5. If a[i][j] equals both min and max, it is the smallest in its row and the largest in its column: print it with its row and column, and add 1 to count.
6. After all the elements have been checked, if count is 0 print NO SADDLE POINT.

Program

Everything is written inside main: the input, the display, and the nested loops that find the row minimum and the column maximum and compare them with the element.

import java.util.Scanner;
public class SaddlePoint
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);        // reads from the keyboard
        System.out.print("Enter rows and columns: ");
        int m = sc.nextInt();                       // number of rows of the matrix
        int n = sc.nextInt();                       // number of columns of the matrix
        if (m < 2 || m > 10 || n < 2 || n > 10)     // order must lie between 2 and 10
        {
            System.out.println("Invalid size");
        }
        else
        {
            int a[][] = new int[m][n];              // create the array of the given order
            System.out.println("Enter the elements:");
            for (int i = 0; i < m; i++)             // i moves over the rows
            {
                for (int j = 0; j < n; j++)         // j moves over the columns
                {
                    a[i][j] = sc.nextInt();
                }
            }
            System.out.println("Matrix:");
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    System.out.print(a[i][j] + "\t");
                }
                System.out.println();               // new line after each row
            }
            int count = 0;                          // number of saddle points found
            for (int i = 0; i < m; i++)
            {
                int min = a[i][0];                  // smallest element of row i: assume the first is the smallest
                for (int j = 1; j < n; j++)
                {
                    if (a[i][j] < min)
                    {
                        min = a[i][j];
                    }
                }
                for (int j = 0; j < n; j++)
                {
                    int max = a[0][j];              // largest element of column j: assume the first is the largest
                    for (int k = 1; k < m; k++)
                    {
                        if (a[k][j] > max)
                        {
                            max = a[k][j];
                        }
                    }
                    if (a[i][j] == min && a[i][j] == max)
                    {
                        System.out.println("Saddle point = " + a[i][j] + " at row " + i + ", column " + j);
                        count++;
                    }
                }
            }
            if (count == 0)
            {
                System.out.println("NO SADDLE POINT");
            }
        }
    }
}

Variable description table

Sample input and output

Enter rows and columns: 3 3
Enter the elements:
1 2 3
4 5 6
7 8 9
Matrix:
1	2	3	
4	5	6	
7	8	9	
Saddle point = 7 at row 2, column 0

Enter rows and columns: 2 2
Enter the elements:
3 1
2 4
Matrix:
3	1	
2	4	
NO SADDLE POINT

Enter rows and columns: 3 3
Enter the elements:
3 1 2
2 0 1
1 1 4
Matrix:
3	1	2	
2	0	1	
1	1	4	
Saddle point = 1 at row 0, column 1
Saddle point = 1 at row 2, column 1

Enter rows and columns: 1 3
Invalid size

Dry run

Take the matrix with rows 3 1 2, 2 0 1, 1 1 4 (the third sample). The row minima are 1, 0, 1 and the column maxima are 3, 1, 4.

count is 2, so the program prints the saddle point 1 at row 0, column 1 and the saddle point 1 at row 2, column 1, the same as the third sample run.

Variations

1. Reverse definition "Find the element that is the maximum in its row and the minimum in its column."
2. Square matrix "Accept a square matrix of size n x n, where n is greater than 2 and less than 10, and display its saddle point, if any."
3. Row minimum and column maximum "Display the smallest element of every row and the largest element of every column of a matrix."