## Amazon Interview Question

Country: India

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.length > 0) : "Empty matrix!";
int m = matrix.length, n = matrix.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.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:

``````matrix =
1, 2, 3
4, 6, 7
5, 8, 9
K = 5
Output = 5.``````

``````matrix =
1, 2, 3
4, 5, 6
7, 8, 9
K = 5
Output = 5.``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

does not work if k =1 or 2, I guess getPivot needs to be fixed for that.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Yup the solution is totally wrong :(

Comment hidden because of low score. Click to expand.
0
of 0 vote
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...
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Nice idea. But the complexity seems a bit high to me. For a n-by-n matrix:

Removing one number requires O(n) swapping, and
n^2/2 numbers need to be removed until the median is reached.
So complexity is O(n^3).

Correct me if I'm wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
a = 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.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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.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];
}else if(i == hr){
index temp = new index();
temp.row = hr;
temp.col = hc/2;
temp.val = mat[temp.row][temp.col];
}else{
index temp = new index();
temp.row = i;
temp.col = n/2;
temp.val = mat[temp.row][temp.col];
}
}

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;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0

Failed! The median of the following matrix:

``````1 2 3
4 6 7
5 8 9``````

is 5 but your algo returns 6.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

I thinks @chriscow's interpretation of the problem is correct.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.