Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Assume we use binary search row by row (or column by column, depends on whether number of rows or columns are less), the time complexity can be compute as O(nlogn).
We can also use the quality of this 2D array that all rows and columns sorted.
I think, first, change the 2D array into a square matrix by adding 0 or other elements that is less than the smallest element.
Second, compare the number we are searching to the value of array[row/2, column/2].
Third, if it bigger than that, recursively call this function for the following three square matrix array[row/2+1..row, 0..column/2], arrat[row/2+1..row, column/2+1..column] and array[0..row/2, column/2+1..column].
The time complexity of this search is estimated of O(3logn).
Of course, if the number of rows or column is relatively smaller than 4, using binary search row by row(column by column) is better.
1) Start with top right element
2) Loop: compare this element e with x
….i) if they are equal then return its position
…ii) e < x then move it to down (if out of bound of matrix then break return false)
..iii) e > x then move it to left (if out of bound of matrix then break return false)
3) repeat the i), ii) and iii) till you find element or returned false
Time Complexity: O(m+n)
The code that works !!!!
#include "stdio.h"
#include<conio.h>
#define ROW 4
#define COL 4
using namespace std;
void searchfrom2d(int a[4][4], int num)
{
int j=COL-1;int i=0;int done =0;
while(i<ROW && j>0)
{
if(a[i][j]<num)
i++;
else j--;
if(a[i][j]==num)
{
done =1;
printf("num is in row-%d and in col-%d\n",i+1,j+1); }
}
if(done==0)
printf("not found");
}
int main()
{
int arr[ROW][COL] = {
{1,3,5,6},
{2,4,7,8},
{9,10,12,14},
{11,13,15,16},
};
searchfrom2d(arr,15);
getch();
return 0;
}
You could also use Binary search in matrix.
private bool FindXMatrix(int[][] m, int x, int row, int col)
{
if (row > m[0].Length-1 || col < 0)
return false;
if (x > m[row][col])
row++;
else if(x<m[row][col])
col--;
else
return true;
bool result = FindXMatrix(m,x, row, col);
return result;
}
What row, col you are using while calling the function first time?
If you use actual row, col... i don;t think it's goona work ... please check.
What row, col you are using while calling the function first time?
If you use actual row, col... i don;t think it's goona work ... please check.
I pass row as 0 and col as row[0].length. So we start from top right, and either go down or left depending on if the X is greater or lesser than current top right. This is same as CTCI book solution
Question - (1) can there duplicates? (2) the question says all rows and all columns sorted, but not that the matrix is sorted. so does this allow say last element of row[i] to exceed first element of the row[i+1] ?
Yes. Duplicates can exist. First occurance of the element would suffice. If all rows and all columns sorted, I think matrix should be sorted. Min element would be at top left corner and max element would be at bottom right corner.
for question (2) lets consider an example-
A = { 2, 4, 6
3, 5, 7
9, 10, 11 }
Although each row and each column is sorted in itself, the entire matrix is not sorted in any particular order.
For instance, A[1][3] > A[2][1]
versus A[2][3] < A[3][1] - this contradicts the assumption that if each row and each column is sorted, the matrix is probably sorted too.
Makes me think that some of the solution posted above might not fit this scenario and have been designed assuming the matrix is sorted.
My approach to solving the problem would be to along the diagonal from A[1][1] to A[n][n]. Compare each of them with the element being searched (say num).
1) If the A[i][j] < num (here i=j), increment both i and j.
2) If A[i][j] > num -
(i) decrement j (keeping i constant) and compare with num (until j=1). Essentially comparing each element 0 through j, on row i.
(ii) if element not found in step (i) above, then decrement i, set j =n, and using a while/for loop decrement j and compare with num (while j > i). This will compare each element of the previous row from the end until the diagonal element is reached.
(iii) if num is not found in (i) or (ii) above, then element does not exist.
A = { 2, 4, 6
3, 5, 7
9, 10, 11 }
lets say we are looking for 7 in A
iteration 1: A[1][1] = 2; 2<7, increment i, j
iteration 2: A[2][2] = 5; 5<7, increment i, j
iteration 3: A[3][3] = 11; 11>7; keep i constant, decrement j
(i) A[3][2] = 10; 10!= 7; decrement j
A[3][1] = 7; 9!=7; decrement j; j=0 - follow (ii)
(ii) decrement i; set j=n; i=2; j=3
A[2][3] = 7; 7=7 - element num found at A[2][3]- exit
Assume we use binary search row by row (or column by column, depends on whether number of rows or columns are less), the time complexity can be compute as O(nlogn).
We can also use the quality of this 2D array that all rows and columns sorted.
I think, first, change the 2D array into a square matrix by adding 0 or other elements that is less than the smallest element.
Second, compare the number we are searching to the value of array[row/2, column/2].
Third, if it bigger than that, recursively call this function for the following three square matrix array[row/2+1..row, 0..column/2], arrat[row/2+1..row, column/2+1..column] and array[0..row/2, column/2+1..column].
The time complexity of this search is estimated of O(3logn).
Of course, if the number of rows or column is relatively smaller than 4, using binary search row by row(column by column) is better.
we can do it in O( Max(logN , logM))
explaination :
1. use 3 variables to store
intialize 1. to A[0][0]
2. to A[0][m-1]
3. to A[n-1][m-1]
2. use search similar to binary search b/w 1. and 2. to find in which col. element is there
3. use search similar to binary search b/w column_numbet_starting_element and 3. to find in in which row ( even exact )element .
time complexity := O( Max ( logN ,logM)).
ALGO
--------
Cover elements diagonally till diagonal element is less than the element being searched and there are more elements in diagonal. Post that if there are remaining rows or columns, cover all the elements there.
COMPLEXITY
-----------------
Max(m,n)
PSEUDOCODE
--------------------
void SearchSorted2D(int a[], int r, int c, int x)
{
i=0;j=0;
while (i<r || j<c)
{
if a[i][j]==x
print(i,j)
else if(a[i][j]>x)
if(a[i][j-1]==x)
print(i,j-1)
else if(a[i-1][j]==x)
print(i-1,j)
if(a[i][j]>x && a[i][j-1]>x && a[i-1][j]>x)
{
print(element not there);
break;
}
// To address the case of m x n where m!=n
if(i!=r-1)
i++;
if(j!=c-1)
j++;
}
}
let say in a 2D array named arr, no. of rows = x and no. of columns = y and the element to be found is z.
search(arr,0,y-1,z)
void search(int[][] array, int i,int j, int target) {
if(array[i][j] == target) {
System.out.println("Element found at:array[" + i + "][" + j + "]");
return;
}
if(target<array[i][j])
search(array,i,--j,target);
else
search(array,++i,j,target);
}
this the code for any rendom unshorted 2-d array finding row n column of any element
#include<stdio.h>
main()
{
int a[100][100];
int i,j,n,m,b,k=1,num;
printf("first give the size of array\n");
printf("no. of row\n");
scanf("%d",&n);
printf("no.of column\n");
scanf("%d",&m);
printf("\n \n");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
printf("%3d",a[i][j]);
printf("\n");
}
printf("\n \n");
for(i=0;i<n;i++)
for(k=1;k<m;k++)
for(j=0;j<m-k;j++)
{
if(a[i][j]>a[i][j+1])
{
b=a[i][j];
a[i][j]=a[i][j+1];
a[i][j+1]=b;
}
}
for(i=0;i<n;i++)
{ for(j=0;j<m;j++)
printf("%3d",a[i][j]);
printf("\n");
}
printf("find the element in 2-d array\n");
scanf("%d",&num);
printf("\n \n \n \n \n");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(a[i][j]==num)
printf("row==%d colom==%d \n",i+1,j+1);
}
}
public static boolean find(int a[][],int rows,int cols,int x)
- AJ March 09, 2012{
int m=0;
int n=cols-1;
while(m<rows&&n>=0)
{
if(a[m][n]==x)
return1;
else if(a[m][n]>x)
n--;
else m++;
}
}