Search In A Row Wise And Column Wise Sorted Matrix in java

You are given an N * N matrix of integers where each row and each column is sorted in increasing order. You are given a target integer ‘X’. Find the position of ‘X’ in the matrix, if it exists then print the pair {i, j} where ‘i’ represents the row and ‘j’ represents the column of the array, otherwise print {-1,-1} For example: If the given matrix is: [ [1, 2, 5], [3, 4, 9], [6, 7, 10]] We have to find the position of 4. We will print {1,1} since A[1][1] = 4.

Input Format : The first line of input contains a single integer ‘T’, representing the number of test cases or queries to be run. Then the ‘T’ test cases follow. The first line of each test case contains two space-separated integers ‘N’ and ‘X’, representing the size of the matrix and the target element respectively. Each of the next ‘N’ lines contains ‘N’ space-separated integers representing the elements of the matrix.

Output Format : For each test case, print the position of ‘X’, if it exists, otherwise print “-1 -1”.

Constraint : 1 ≤ T ≤ 10 1 ≤ N ≤ 10^3 1 ≤ X ≤ 10^6 1 ≤ Aij ≤ 10^6

where ‘T’ is the number of test cases, ‘N’ is the number of rows and columns, ‘X’ is the target value, and Aij is the elements of the matrix.

Sample Input 1 : 2 3 4 1 2 5 3 4 9 6 7 10 2 5 4 5 8 6

Sample Output 1 : 1 1 0 1

Explanation Of Input 1: The first test case is already explained in the problem statement. The second test case, the given matrix is: [[4, 5], [5, 6]] We have to find the position of 5. So we return {0,1}.

Sample Input 2 : 2 3 16 2 4 8 3 6 9 4 7 16 1 10 4

Sample Output 2 : 2 2 -1 -1

Solution:–

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
public static void search(int[][] mat,
int n, int x)
{

// set indexes for top right
int i = 0, j = n - 1;
// element

while (i < n && j >= 0)
{
        if (mat[i][j] == x)
        {
                System.out.println(i + " " + j);
                return;
        }
        if (mat[i][j] > x)
                j--;
        else // if mat[i][j] < x
                i++;
}

        System.out.println("-1 -1");
        
return; // if ( i==n || j== -1 )
}
        
public static void main (String[] args) throws java.lang.Exception
{

 Scanner sc = new Scanner(System.in);
 int t = sc.nextInt();
        
while( t-- > 0)
{
        int n = sc.nextInt();
        int x = sc.nextInt();
       int [][]arr = new int[n][n];

        for(int i=0; i<n; i++)
        {
                for(int j=0; j<n;j ++){
                     arr[i][j] = sc.nextInt();
                }
        }
        search(arr, n, x);
        }
   }
}