Amazon Interview Question
Country: India
Algo... Time complexity O(N+M)
say matrix dim N, M.
start with i = 0, j = M-1.
Say no. to b searched is x.
then if(Mat[i][j] < x)
i++;
if(Mat[i][j] > x)
j--;
else {
printf("Element found");
return;
}
Keep on doing this till i == N or j < 0.
void search_element(int Mat[][], int N, int M, int x) {
int i = 0, j = M-1;
while(i > N && j >= 0) {
if(Mat[i][j] > x)
j--;
else if(Mat[i][j] < x)
i++;
else {
printf("Element found, i = %d, j = %d\n", i, j);
return;
}
}
printf("Not Found\n");
}
Searching diagonal element is a good approach. My idea is as following:
(1) if data[0][0] < pattern, return false;
(2) while(index < sizeRow){
if (data[index][index] == pattern) return true;
if (data[index][index] > pattern) break;
index++;}
(3) if (index == sizeRow) return false;
else search data[index][0-index] and data[0-index][0]
Complexity is traversal diagonal element is O(N) and search column and Row is 2O(logN)
Total is O(N)
Given is the algo in java
public static void main(String[] args)
{
int[][] mat = {
{1, 4, 7},
{2, 5, 8},
{3, 6, 9},
};
findNum(mat, 9);
}
private static void findNum(int[][] mat, int num)
{
int i = mat.length-1;
int j = 0;
for(;i>=0 && i<mat.length && j>=0 && j<mat[0].length;)
{
if(mat[i][j]==num)
{
System.out.println("Found: (" + i + ", " + j+")");
return;
}
if(num>mat[i][j])
j++;
else
i--;
}
System.out.println("Not Found");
}
Late to the party.. What do you guys think about this? Using Binary search method
int main(){
int sample[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
int target = 6;
int lowX, highX, lowY, highY, midX, midY;
//Note: some values are hardcoded, should not matter.
lowX = 0;
highX = 2;
lowY = 0;
highY = 3;
if(target <= sample[0][0] || target >= sample[3 - 1][4 - 1]){
std::cout<<"Nope";
}
while(lowX <= highX && lowY <= highY){
midX = (lowX + highX)/2;
midY = (lowY + highY)/2;
if(target < sample[midX][midY]){
highX = midX - 1;
highY = midY - 1;
}
else if(target > sample[midX][midY]){
lowX = highX + 1;
lowY = highY + 1;
}
else {
lowX = highX + 1;
lowY = highY + 1;
}
}
if(target == sample[midX][midY]){
std::cout<<"Found";
}
else{
std::cout<<"Nope";
}
return 0;
}
diagonal search can't guarantee you to find the element.
1, 4, 7
2, 5, 8
3, 6, 9
To find 7, you won't find it by searching diagonally.
1, 4, 7
2, 5, 8
3, 6, 9
to
3, 6, 9
2, 5, 8
1, 4, 7
now, starting from (0,0), < go down, > go right, done
Do search from the right corner. For example in the following matrix 1,4,7
2,5,8
3,6,9 and number to be searched is 5
Check if mat[0][2] > number to searched then decrement col to col -1
else increment row - row + 1.
Do this until u reach col as 0 and row as max .. Either u ll find the element in the middle
1.traverse 1st row:
- Anonymous November 09, 2012if found, return;
else if (any a[0][i]>number) traverse i-1 column
if found return;
2.
traverse 1st column:
if found return;
else if(any a[i][0]>num)
traverse "i-1"th row: if found return;
time complexity :2(m+n) ie O(m+n);