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); } } }

## Add a Comment