Last Updated: 30 Oct, 2020
Search In A Row Wise And Column Wise Sorted Matrix
Moderate
Asked in companies
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.
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.
Approaches
- 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}.
- Run a loop from j = 0 to N - 1, to check each element of the row.
- If the element is not found in the entire matrix, return {-1, -1}
- Run a loop for each column, i.e. iterate through each column.
- Using binary search on each row, find if the element exists in the current row.
- Binary Search is done because each row is sorted.
- If the element is not found in the entire matrix, return {-1, -1}
- Start your search from the top-right corner of the matrix.
- There can be three cases:
- The current element is equal to target: return this position
- The current element is greater than the target: This means that any element on the current column is also greater, thus we move to the previous column
- The current element is smaller than the target: This means that any element on the current row is also smaller, thus we move to the next row
- If we go out of the matrix, it means element is not found. So, return {-1, -1}.
Similar problems