## Amazon Interview Question

SDE-2s**Team:**Hyderabad

**Country:**India

**Interview Type:**Phone Interview

Run Binary Search on first column until one row is left and then run Binary Search on that one row O(logr + logc) {r : number of rows, c : number of columns}

```
static private int BinarySearch(int[][] mat, int a, int rs, int cs, int ce){
if(cs > ce)
return -1;
int[] arr = mat[rs];
int mid = cs + (ce - cs)/2;
if(arr[mid] == a)
return 1;
if(arr[mid] > a)
return BinarySearch(mat, a, rs, cs, mid - 1);
else
return BinarySearch(mat, a, rs, mid + 1, ce);
}
static private int rec(int[][] mat, int a, int rs, int re, int cs, int ce){
if(rs > re)
return -1;
if(re - rs == 0)
return BinarySearch(mat, a, rs, cs, ce);
int rm = rs + (re - rs)/2 + 1;
if(mat[rm][0] == a)
return 1;
if(mat[rm][0] > a)
return rec(mat, a, rs, rm - 1, cs, ce);
else
return rec(mat, a, rm, re, cs, ce);
}
static public int bs2d(int[][] mat, int a){
int r = mat.length;
int c = mat[0].length;
if(r == 0 || c == 0)
return -1;
return rec(mat, a, 0, r - 1, 0, c - 1);
}
```

There are two approaches possible: The first one is: Perform a binary search vertically (Which takes O ( N )) and then perform a binary search inside the row found (which takes O (M)). Since O (N) + O(M) takes O (N*M) then we can say that it's like performing a binary search over a huge array that is composed of segments made of rows. So that

BigArray[i] = matrix[i / M, i % M]. So it's simpler to peform a binary search over the BigArray.

/*

0-> x x x x x->4

x x x x x

x x x x x 15 -> (3,0) m=x/5 n=x%5

x x x x x->19

*/

class Search{

public static void main(String[] args){

Search s=new Search();

int[] a={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};

int x=15;

s.find(x,4,5,a);

}//end of main

void find(int x,int m,int n,int[] a){

int start=0;

int end=n*m-1;

binarySearchC(x,a,start,end);

return;

}//end of find

void binarySearchC(int x,int[] a,int s,int e){

if(s<e){

int m=(s+e)/2;

if(x==a[m]){

System.out.println(m/5+" , "+m%5);

return;

}else if (x<a[m]){

binarySearchC(x,a,s,m);

}else{

binarySearchC(x,a,m,e);

}//end of else

}//end of if

}//end of binarySearch

}//end of class

Recursive C# code for this question.

Explanation on comments in-line.

```
static bool Search(int num, int[,]matrix,int m,int n) //m: number of rows, n: number of columns
{
if (num < matrix[0, 0] || num > matrix[m - 1, n - 1]) return false;
return SearchUtil(num, matrix,0, m, 0, n);
}
static bool SearchUtil(int num, int[,]matrix,int minI,int maxI, int minJ,int maxJ)
{
while (minI<=maxI)
{
int midI = (minI + maxI) / 2;
int midJ = (minJ + maxJ) / 2;
if (matrix[midI, midJ] == num)
return true;
if (num > matrix[midI, midJ]) //If the number is greater than the middle element, it's either on the same row on middle's right side, or the next rows anywere.
{
if (num <= matrix[midI, maxJ - 1]) //if it's smaller or equal to the largest element in this row;
{
return SearchUtil(num, matrix, midI, midI, midJ, maxJ); //it's on the same row, to the right of the middle element.
}
else //if it's bigger than the middle element;
{
return SearchUtil(num, matrix, midI + 1, maxI, 0, maxJ); //it's for sure on one of the next rows.
}
}
if (num < matrix[midI, midJ]) //If the number is smaller than the middle element, it's either on the same row on middle's left side, or the previous rows anywere.
{
if (num >= matrix[midI, 0]) //if it's greater or equal to the smallest element in this row;
{
return SearchUtil(num, matrix, midI, midI, 0, midJ); //it's on the same row, to the left of the middle element.
}
else
{
return SearchUtil(num, matrix, 0, midI - 1, 0, maxJ); //it's for sure on one of the previous rows.
}
}
}
return false;
}
```

- apt4790 January 31, 2017