Amazon Interview Question
0of 0 votesGiven a sorted 2D matrix. Find the median.
Country: India
Complexity analysis for n-by-n matrix:
Just like in QuickSelect, with good pivots, it will take O(log(n^2)) = O(logn) recursions. In each recursion, it takes O(nlogn) to find the new pivot using PriorityQueue (essentially doing heapsort), and O(n) for partitioning the matrix with the pivot.
So complexity is O(n^2 logn).
Its just my thought and I am not sure if this will work
Solution 1:
If we consider ith row and ith column to be a chunk, then the top right element in the inverted L will be the median. Then use the concept similar to median of median algorithm to eliminate the top chunk and bottom chunk and follow procedure similar to median of median algo
Solution 2:
With the below method we might be more efficient, but the algo is not complete
Sort the elements in the leading diagonal. In case n is odd, the middle element will be the median.
In case n is even, we need to find all the elements between the 2 middle elements which will give us the median. ( Little more time as to be invested to come up with a precise algorithm for this part)
Once you start think about the diagonal, you are on the WRONG track. The median does not need to be on either the diagonal or the anti-diagnoal. Like this:
1 2 3 101 102
4 5 6 103 104
7 8 9 105 106
10 11 107 108 109
12 50 110 111 112
50 is the median.
Use heap operations. repeat removing the first number and swap until you find the median.
1 2 3 101 102
4 5 6 103 104
7 8 9 105 106
10 11 107 108 109
12 50 110 111 112
Remove 1
2 3 6 101 102
4 5 9 103 104
7 8 105 106 109
10 11 107 108 112
12 50 110 111
Repeat removing 2, 3 and count...
Code for Heap extractMin operation described by Jim:
NOTE- Median when n is odd is assumed to be at floor(n/2).
public static int extractMin(int [][] a) {
int result = a[0][0];
a[0][0] = Integer.MAX_VALUE;
int imin=0, jmin=0, icur=0, jcur=0;
while(true) {
if(icur+1 < a.length && a[icur+1][jcur] <= a[imin][jmin]) {
imin = icur+1;
jmin = jcur;
}
if(jcur+1 < a[0].length && a[icur][jcur+1] <= a[imin][jmin]) {
imin = icur;
jmin = jcur+1;
}
if(imin == icur && jmin == jcur) {
break;
}
else {
//System.out.println("Swapping "+imin+","+jmin+" with "+icur+","+jcur);
int temp = a[imin][jmin];
a[imin][jmin] = a[icur][jcur];
a[icur][jcur] = temp;
icur = imin;
jcur = jmin;
}
}
return result;
}
Result for:
1 2 3 101 102
4 5 6 103 104
7 8 9 105 106
10 11 107 108 109
12 50 110 111 112
is 12.
public static int KthSmallest2D(){
int[][] matrix = {{1,2,3,101,102}, {4,5,6,103,104}, {7,8,9,105,106}, {10,11,107,108,109}, {12,50,110,111,112}};
int pivot = 0, lr=0, lc=0, m=matrix.length-1, n= matrix[0].length-1, hr = m, hc = n;
int K = 13, num = 0;
while(lr <= hr && lr <= m){
index pi = get2DPivot(matrix, lr, lc, hr, hc, m,n);
pivot = pi.val;
index ix = get2DPartition(matrix, lr, lc, hr, hc, pi, m ,n);
num = (n+1)*ix.row+ix.col;
if(num == K-1 )
return pivot;
else if(num < K-1){
if(ix.col == n){
lr = ix.row + 1;
lc = 0;
}else{
lr = ix.row;
lc = ix.col + 1;
}
}else{
if(ix.col == 0){
hr = ix.row - 1;
hc = n;
}else{
hr = ix.row;
hc = ix.col-1;
}
}
}
return -1;
}
public static index get2DPivot(int[][] mat, int lr, int lc, int hr, int hc, int m, int n){
index pivot = new index();
ArrayList<index> ar = new ArrayList<index>();
for(int i = lr; i<= hr; i++){
if(i == lr){
index temp = new index();
temp.row = lr;
if(lr != hr)
temp.col = lc+ (n-lc)/2;
else
temp.col = lc+ (hc-lc)/2;
temp.val = mat[temp.row][temp.col];
ar.add(temp);
}else if(i == hr){
index temp = new index();
temp.row = hr;
temp.col = hc/2;
temp.val = mat[temp.row][temp.col];
ar.add(temp);
}else{
index temp = new index();
temp.row = i;
temp.col = n/2;
temp.val = mat[temp.row][temp.col];
ar.add(temp);
}
}
int size = ar.size();
pivot = ar.get(size/2);
return pivot;
}
public static index get2DPartition(int[][] mat, int lr, int lc, int hr, int hc, index pivot, int m, int n){
index ix = new index();
// swap pivot with hr, hc
int temp = mat[hr][hc];
mat[hr][hc] = pivot.val;
mat[pivot.row][pivot.col] = temp;
int j= lr,k = lc;
while(true){
while(!(j == hr && k == hc) && mat[j][k] < pivot.val){
k++;
if(k > n){
j++;
k =0;
}
}
int c = (hc-1 >= 0)?hc-1:n;
int r = (hc-1 >= 0)?hr:hr-1;
while(!(r == j && c == k) && mat[r][c] >= pivot.val){
c--;
if(c < 0){
r--;
c = n;
}
}
if( j < r || (j == r && (k < c))){
temp = mat[r][c];
mat[r][c] = mat[j][k];
mat[j][k] = temp;
}else{
mat[hr][hc] = mat[j][k];
mat[j][k] = pivot.val;
break;
}
}
ix.row = j;
ix.col = k;
ix.val = pivot.val;
return ix;
}
if(row%2!=0&&col%2!=0){// if odd number of element
int midRow= row/2;
int midCol=col/2;
System.out.println("median is : "+matrix[midRow][midCol]);
}
else //if even number of elements
{
int midrow1=0,midrow2=0,midcol1=0,midcol2=0;
if(row%2==0){
midrow1=row/2;
midrow2=midrow1-1;
}
if(row%2!=0){
midrow1=row/2;
midrow2=midrow1;
}
if(col%2==0){
midcol1=col/2;
midcol2=midcol1-1;
}
if(col%2!=0){
midcol1=col/2;
midcol2=midcol1;
}
int median = matrix[midrow1][midcol1]+matrix[midrow2][midcol2];
System.out.println("median is elseloop :"+median/2);
}
Failed! The median of the following matrix:
1 2 3
4 6 7
5 8 9
is 5 but your algo returns 6.
By "Sorted 2D array", it usually only means that each row and column is sorted! It only means:
matrix[i][j] <= matrix[i][j+1] and matrix[i][j] <= matrix[i+1][j]
That's it! Nothing more! Otherwise the question is just way toooooooooooooooo trivial to be an Amazon interview question.
Educate yourself about "Young Tableau" on wikipedia.
We can do something similar to the QuickSelect approach for finding the K-th smallest element of an unsorted 1D array. In QuickSelect:
1. Pick a pivot
2. Partition the 1D array into "< pivot" and "> pivot"
3.1 If # "< pivot" == K-1, pivot is the K-th element.
3.2 If # "< pivot" < K-1, pick a new pivot in the "> pivot" partition and repeat.
3.3 If # "< pivot" > K-1, pick a new pivot in the "< pivot" partition and repeat.
With random pivot, the mean complexity is O(n) in an array of size n.
For this problem, given matrix M[][] of m rows and n columns, sorted both row- and column-wise. We can do this:
1. Pick a pivot
2. Start a walk from the top-right of M, move left if current element >= pivot, move down otherwise.
3. The left-most element in each row visited in step 2 partitions M into "< pivot" and "> pivot". Pick the new pivot similar to the 1D case.
Here is my complete Java code:
import java.util.PriorityQueue; public class kSelect2DMatrix { public static int kSmallest2D (int[][] matrix, int K) { assert ( matrix.length > 0 && matrix[0].length > 0) : "Empty matrix!"; int m = matrix.length, n = matrix[0].length; int scan_row, scan_col; int pivot, smallerThanPivot; /* Use two arrays to keep track of * the left and right boundaries (inclusive) of the candidates in each row */ int[] left = new int[m]; int[] right = new int[m]; for (int i = 0; i<m; i++) { left[i] = 0; right[i] = n-1; } while (true) { pivot = getPivot(matrix, left, right); scan_row = 0; scan_col = n - 1; smallerThanPivot = 0; //Keep track of the last element < pivot (starting from left) in each row int[] lastSmallerThanPivot = new int[m]; for (int i = 0; i < m; i++) lastSmallerThanPivot[i] = -1; while (scan_row < m && scan_col >= 0) { if ( matrix[scan_row][scan_col] >= pivot ) scan_col--; //move left else { //scan_col+1 elements in the scan_row-th row are smaller than pivot lastSmallerThanPivot[scan_row] = scan_col ; scan_row++; //move down } } //if exit the inner while loop with scan_col < 0 in the scan_row-th row //the scan_row-th row and the rows below have no element smaller than pivot for (int i = 0; i < m; i++) smallerThanPivot += (lastSmallerThanPivot[i] + 1); if (smallerThanPivot == K - 1) //found the K-th element return pivot; else if (smallerThanPivot < K - 1) { /* Current pivot is too small. * The K-th element cannot be to the elements <= lastSmallerThanPivot[i] in row i * Update left boundary. */ for (int i = 0; i < m; i++) left[i] = Math.max(left[i], lastSmallerThanPivot[i]+1); } else { /* Current pivot is too large. * The K-th element cannot be to the elements > lastSmallerThanPivot[i] in row i * Update right boundary. */ for (int i = 0; i < m; i++) right[i] = Math.min(right[i], lastSmallerThanPivot[i]); } } } public static int getPivot(int[][] matrix, int[] left, int[] right) { PriorityQueue<Integer> queue = new PriorityQueue<Integer>(); for (int i = 0; i < left.length; i++) { if (left[i] < matrix[0].length) queue.add(matrix[i][left[i] + (right[i] - left[i]) / 2]); } int qSize = queue.size(), pivot=0; for (int i = 0; i <= qSize/2; i++) pivot = queue.poll(); return pivot; } public static void main(String[] args) { int[][] matrix = {{1, 2, 3}, {4, 6, 7}, {5, 8, 9}}; System.out.println(kSmallest2D(matrix, 5)); } }Test case:
- chriscow January 27, 2014