1. Write a program to declare a square matrix A[ ][ ] of order N (N<20).
2. Allow the user to input positive integers into this matrix. Perform the following tasks on the matrix.
3. Output the original matrix.
4. Find the SADDLE POINT for the matrix. A saddle point is an element of the matrix such that it is the minimum element for the row and the maximum element for the column to which it belongs. Saddle point for a given matrix is always unique. If the matrix has no saddle point, output the message "NO SADDLE POINT".
5. If the matrix has a saddle point element then sort the elements of the left diagonal in ascending order using insertion sort technique. All other elements should remain unchanged.

Test your program for the following data and some random data:

Sample data:

Input:
n = 4

Matrix A[ ][ ]
2	5	6	9
8	4	12	3
6	7	3	1
12	24	2	11

Output:

Matrix A[ ][ ]
2	5	6	9
8	4	12	3
6	7	3	1
12	24	2	11

No Saddle Point

Matrix after sorting the Principal diagonal:

2	5	6	9
8	3	12	3
6	7	4	1
12	24	2	11

Input:
n = 3

Matrix A[ ][ ]
4	6	12
2	8	14
1	3	6

Output:

Matrix A[ ][ ]
4	6	12
2	8	14
1	3	6

Saddle Point = 4

Matrix after sorting the Principal diagonal:

4	6	12
2	6	14
1	3	8

import java.util.Scanner;

public class KboatDDASaddlePoint
{
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter the size of the matrix: ");
        int n = in.nextInt();
        
        if (n >= 20) {
            System.out.print("Size is out of range");
            return;
        }
        
        int a[][] = new int[n][n];
        
        System.out.println("Enter elements of the matrix: ");
        for (int i = 0; i < n; i++) {
            System.out.println("Enter Row "+ (i+1) + " :");
            for (int j = 0; j < n; j++) {
                a[i][j] = in.nextInt();
                if (a[i][j] < 0) {
                    System.out.print("Invalid Input");
                    return;
                }
            }
        }
        
        System.out.println("Matrix A[ ][ ]");
        printMatrix(a, n, n);
        
        //Find the Saddle Point
        boolean found = false;
        for (int i = 0; i < n; i++) {
            int rMin = a[i][0];
            int cIdx = 0;
            
            for (int j = 1; j < n; j++) {
                if (rMin > a[i][j]) {
                    rMin = a[i][j];
                    cIdx = j;
                }
            }
            
            int k = 0;
            for (k = 0; k < n; k++) {
                if (rMin < a[k][cIdx]) {
                    break;
                }
            }
            
            if (k == n) {
                found = true;
                System.out.println("Saddle Point = " + rMin);
                break;
            }
        }
        
        if (!found) {
            System.out.println("No Saddle Point");
        }
        
        //Sort Left Diagonal with Insertion Sort
        for (int i = 1; i < n; i++) {
            int key = a[i][i];
            int j = i - 1;
            
            while (j >= 0 && a[j][j] > key) {
                a[j + 1][j + 1] = a[j][j];
                j--;
            }
            
            a[j + 1][j + 1] = key;
        }
        
        System.out.println("Matrix after sorting the Principal diagonal:");
        printMatrix(a, n, n);
    }
    
    public static void printMatrix(int arr[][], int m, int n) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }
}