Search in a row wise and column wise sorted matrix
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”.

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

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.

Question

Search in a row wise and column wise sorted matrix

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”.

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

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.

Accepted Answer

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}

Space Complexity: O(1)Explanation:

O(1).

Since only constant extra space is required.

Time Complexity: O(n^2)Explanation:

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).

Accepted Answer

Binary Search

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}

Space Complexity: O(1)Explanation:

O(1).

Since only constant extra space is required.

Time Complexity: O(nlogn)Explanation:

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

The binary search takes log N time. We are applying binary search for at most ‘N’ columns. Hence, the overall time complexity is O(N log N).

Accepted Answer

Optimal Solution

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}.

Space Complexity: O(1)Explanation:

O(1).

Since only constant extra space is required.

Time Complexity: O(n)Explanation:

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

In the worst case, only one traversal from top right corner to bottom left corner is needed, i.e, i from 0 to N - 1 and j from N - 1 to 0 with at most 2*N steps.

For example: If the given matrix is:

Input Format:

Output Format:

Constraints:

Note:

Top Amadeus Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amadeus Software Developer