ISC Practicals and Theory - Saddle Point (OOP)

A saddle point of a matrix is an element that is the smallest in its row and the largest in its column. This version is written as a class SaddlePoint with data members, a parameterised constructor and methods that each do one job; main reads the order, creates an object and calls the methods. It prints the matrix and every saddle point with its position, or NO SADDLE POINT.

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 the maximum of column j. Some books use the reverse (the maximum of the row and the minimum of the column); this program uses the minimum of the row and the maximum of the column.

Example: for the rows 1 2 3, 4 5 6, 7 8 9, the element 7 at row 2, column 0 is the smallest in its row and the largest in its column.

An element equal to the row minimum and the column maximum counts, so repeated values are allowed, and a matrix can have more than one saddle point only if they have equal values.

Algorithm

1. main reads the number of rows r and columns c. If either is less than 2 or more than 10, it prints Invalid size and stops.
2. Otherwise main creates the object ob with new SaddlePoint(r, c). The constructor stores the order in m and n and creates the array a[m][n].
3. readMatrix(sc) reads the elements with two nested loops.
4. display() prints the matrix row by row.
5. findSaddle() sets count = 0 and visits every element a[i][j]:
   • it calls isSaddle(i, j);
   • if that returns true, it prints the value with its row and column and adds 1 to count.
6. isSaddle(r, c) returns true when a[r][c] equals both rowMin(r) and colMax(c).
7. rowMin(r) and colMax(c) compare the first element of the row or column with the rest to find the smallest or largest.
8. If count is 0 after all elements are checked, findSaddle() prints NO SADDLE POINT.

Positions are array indices counted from 0.

Program

The constructor sets up the array, readMatrix() reads it, display() prints it, rowMin() and colMax() find the two values, isSaddle() decides for one element and findSaddle() prints the answer.

import java.util.Scanner;

/**
 * Class SaddlePoint finds the saddle points of an m x n matrix.
 * A saddle point is an element that is the smallest in its row
 * and the largest in its column.
 */
public class SaddlePoint
{
    int a[][];      // stores the elements of the matrix
    int m;          // number of rows of the matrix
    int n;          // number of columns of the matrix

    /**
     * Parameterised constructor: stores the order and creates the array.
     * Parameters: mm - number of rows, nn - number of columns.
     */
    SaddlePoint(int mm, int nn)
    {
        m = mm;
        n = nn;
        a = new int[m][n];
    }

    /**
     * Reads the elements of the matrix.
     * Parameter sc: the Scanner object that reads from the keyboard.
     */
    void readMatrix(Scanner sc)
    {
        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();
            }
        }
    }

    /**
     * Prints the matrix row by row.
     */
    void display()
    {
        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
        }
    }

    /**
     * Returns the smallest element of row r.
     * Parameter r: the row number (0 to m-1).
     */
    int rowMin(int r)
    {
        int min = a[r][0];                          // assume the first element is the smallest
        for (int j = 1; j < n; j++)
        {
            if (a[r][j] < min)
            {
                min = a[r][j];
            }
        }
        return min;
    }

    /**
     * Returns the largest element of column c.
     * Parameter c: the column number (0 to n-1).
     */
    int colMax(int c)
    {
        int max = a[0][c];                          // assume the first element is the largest
        for (int i = 1; i < m; i++)
        {
            if (a[i][c] > max)
            {
                max = a[i][c];
            }
        }
        return max;
    }

    /**
     * Returns true if the element at row r, column c is a saddle point,
     * that is, it equals the minimum of its row and the maximum of its column.
     */
    boolean isSaddle(int r, int c)
    {
        return a[r][c] == rowMin(r) && a[r][c] == colMax(c);
    }

    /**
     * Prints every saddle point with its position (row and column
     * numbers counted from 0), or a message if there is none.
     */
    void findSaddle()
    {
        int count = 0;                              // number of saddle points found
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (isSaddle(i, j))
                {
                    System.out.println("Saddle point = " + a[i][j] + " at row " + i + ", column " + j);
                    count++;
                }
            }
        }
        if (count == 0)
        {
            System.out.println("NO SADDLE POINT");
        }
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);        // reads from the keyboard
        System.out.print("Enter rows and columns: ");
        int r = sc.nextInt();                       // rows entered by the user
        int c = sc.nextInt();                       // columns entered by the user
        if (r < 2 || r > 10 || c < 2 || c > 10)     // order must lie between 2 and 10
        {
            System.out.println("Invalid size");
        }
        else
        {
            SaddlePoint ob = new SaddlePoint(r, c); // object of the class
            ob.readMatrix(sc);
            ob.display();
            ob.findSaddle();
        }
    }
}

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: 11 3
Invalid size

Dry run

Take the matrix with rows 3 1 2, 2 0 1, 1 1 4 (the third sample). Here r = 3, c = 3, so the constructor creates a $3 \times 3$ array. 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."