Amazon Interview Question Interns
2of 4 votesSearch in a row wise and column wise sorted matrix
Country: India
Interview Type: Phone Interview
can't we do a binary search across rows and column? start at the middle row and move up and down till we narrow down the row and then the same thing on the columns. O(log rows * log cols )
Binary search won't work in this problem.
The catch is that there the target value can be in the range of multiple rows or columns.
Take the example with looking for x=12 in the following matrix:
1, 2, 3, 4, 5
6, 10, 20, 30, 40
7, 11, 21, 31, 41
8, 12, 22, 32, 42
9, 13, 23, 33, 43
You have 4 rows and 4 columns that can potentially contain 12. Which row and column should you continue the iteration in binary search?
I think combination of recursion and binary search can solve this problem easily with O(log rows * log cols ) complexity.
In above case we will start with middle as it is the median of medians in the matrix, so the bottom-right part will be greater than the middle number and top left will be smaller than the middle number. In this way we can eliminate searching 1/4 of the matrix. If we continue doing it recursively with logically changing the matrix sizes and searching them recursively.
In the end we will be left with one row at the bottom of the tree where we need to do the binary search to determine the element.
I will try to code it and see if this works. Please let me know if you there is any problem with this approach .
@id
This got me thinking. This may not be very efficient solution because the recurrence relation 'you think' you have here is T(n) = 4T(N/4) + c (where N = n^2) ~ leading to log<base 4>(n^2) complexity. But it's NOT.
Unlike binary search, this does not result in a decision tree at all, since after dividing in four parts, you may not be able to pinpoint one of the parts to proceed and may end up searching each 1/4 from every decision.
Which means that worst time-complexity, my friend, is 4(n^2/4) ~ n^2 (leaving this as an exercise). Let me know if you need anymore clarification.
sorted in row+column means you can just "flat out" the matrix into an array to do a binary search.
turn:
1 3 4 5
6 6 7 7
9 9 10 10
12 17 29 31
into:
1 3 4 5 6 6 7 7 9 9 10 10 12 17 29 31
we don't need to "physically" rearrange the matrix into an array by coping or something.
As@chriscow made a good point that the biggest problem with binary search is that we don't know what row/column to continue for the iteration. We can work on that:
int nRow = matrix.length;
int nCol = matrix[0].length;
public static int getElementByIdx(int flatMatrixIdx, int[][] matrix, int nRow, int nCol){
int n = nRow * nCol;
if (flatMatrixIdx > n) {
throw new Execption("index out of range");
}
int xRow = idx / nCol;
int xCol = idx - nCol * xRow;
return matrix[xRow][xCol];
}
// do a binary search here
public static void binarySearchOnSortedMatrix(int[][] matrix, int target) {
// blah
}
time complexity will still be O(nRow + nCol), it's just cleaner to understand the process. Actually Matlab provides same method as this to traverse a matrix.
I don't think your understanding about sorted row+column is correct. The following matrix is sorted row+column, but you can't flatten it.
1 2 4 7
3 5 8 11
6 9 12 14
10 13 15 16
Assuming both sorted in strictly increasing order:
Start from the top-right corner of the matrix. If the matrix element is larger than the target, move to the column on the left; if smaller, move to the row below.
Complexity if O(#rows + #columns)
- chriscow January 24, 2014public Position searchSortedMatrix(int x, int[][] M) { if (M.length==0 || M[0].length==0) return Position(-1,-1); int row = 0, column = M[0].length-1, curVal; while (row<M.length && column>=0) { curVal = M[row][column]; if (curVal == x) return Position(row,column); if (curVal > x) column--; else row++; } return Position(-1,-1); }