Saddle Price

1. You are given a square matrix of size 'n'. You are given n*n elements in the square matrix
2. You are required to find the saddle price of the given matrix and print the saddle price
3. The saddle price is defined as the lowest price in the row but the maximum price in the column of the matrix.

Input:

3

4

15 21 23 5

17 16 19 6

22 11 12 8

Output: 8

package jan24;

import java.util.Scanner;

public class SaddlePoint {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);  // TC: O(1), SC: O(1)

        int m = scanner.nextInt();  // TC: O(1), SC: O(1)
        int n = scanner.nextInt();  // TC: O(1), SC: O(1)

        int[][] arr = new int[m][n];  // TC: O(1), SC: O(m * n)

        // Input matrix — TC: O(m * n)
        for (int i = 0; i < m; i++) {           // TC: O(m)
            for (int j = 0; j < n; j++) {       // TC: O(n)
                arr[i][j] = scanner.nextInt();  // TC: O(1)
            }
        }

        getAns(arr); // TC: O(m * (n + m)), SC: O(1)
    }

    private static void getAns(int[][] matrix) {
        int r = matrix.length;       // TC: O(1), SC: O(1)
        int c = matrix[0].length;    // TC: O(1), SC: O(1)

        for (int i = 0; i < r; i++) {     // TC: O(m)

            System.out.println();

            // Find minimum in current row — TC: O(n)
            int minColIndex = 0;         // TC: O(1)
            for (int j = 1; j < c; j++) {    // TC: O(n)
                System.out.println("checking in " + i + ", " + j);
                System.out.println(matrix[i][j] + " < " + matrix[i][minColIndex]);
                if (matrix[i][j] < matrix[i][minColIndex]) {  // TC: O(1)
                    minColIndex = j;  // TC: O(1)
                }
            }

            System.out.println();

            // Check if it's the maximum in its column — TC: O(m)
            boolean isSaddlePoint = true;  // SC: O(1)
            for (int k = 0; k < r; k++) {  // TC: O(m)
                System.out.println(matrix[k][minColIndex] + " < " + matrix[i][minColIndex]);
                if (matrix[k][minColIndex] > matrix[i][minColIndex]) { // TC: O(1)
                    isSaddlePoint = false;  // TC: O(1)
                    break;
                }
            }

            if (isSaddlePoint) {    // TC: O(1)
                System.out.println("Saddle Point: " + matrix[i][minColIndex]); // TC: O(1)
                return;  // TC: O(1)
            }
        }

        System.out.println("No Saddle Point Found");  // TC: O(1)
    }
}

🔍 Overall Complexities:
Time Complexity: O(m * (n + m)) → because for each of m rows:
Finding min in row = O(n)
Checking max in column = O(m)
Space Complexity: O(m * n) → for the input matrix only

Case
Time Complexity
Explanation




Best
O(m * n)
Saddle point is found in the first row, so only one row is processed.


Average
O(m * (n + m)) / 2
On average, saddle point is found midway, so about half the matrix is scanned.


Worst
O(m * (n + m))
No saddle point exists or found at the last row, requiring full scan.