Search In A Row Wise And Column Wise Sorted Matrix

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
71 upvotes
Asked in companies
AdobeOracleMicrosoft

Problem statement

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 return the pair {i, j} where 'i' represents the row and 'j' represents the column of the array, otherwise return {-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 return {1,1} since A[1][1] = 4.
Detailed explanation ( Input/output format, Notes, Images )
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”.

Note:

It is guaranteed that the matrix contains distinct elements.
You are not required to print the expected output, it has already been taken care of. Just implement the function.
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
Constraints:
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.
Time Limit : 1 sec
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
Hint

Can we check each element to find a match?

Approaches (3)
Brute Force
  • Run a loop from i = 0 to N - 1, to check each row.
    • Run a loop from j = 0 to N - 1, to check each element of the row.
      • If there is a match, return {i, j}.
  • If the element is not found in the entire matrix, return {-1, -1}
Time Complexity

O(N ^ 2), where ‘N’ is the number of rows or columns in the matrix.

 

There are a total of N * N elements and we are checking each element for a match. Hence, the overall time complexity is O(N ^ 2).

Space Complexity

O(1).

 

Since only constant extra space is required.

Code Solution
(100% EXP penalty)
Search In A Row Wise And Column Wise Sorted Matrix
Full screen
Console