## Amazon Interview Question Software Engineer / Developers

• 0

Given a 2D array, all rows and all columns sorted. Find an integer x from the 2D array.

Country: United States
Interview Type: Phone Interview

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

public static boolean find(int a[][],int rows,int cols,int x)
{
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++;
}

}

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

After WHILE loop, return 0 if number doesn't exist.

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

not optimal

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

Have to decrement m also for one time

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

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.

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

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)

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

This is the best algorithm for this problem..+1 from my side.

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

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

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

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

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

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.

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

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.

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

Awesome man this works

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

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

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

this is still o(n)

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

Here is my answer to the question:

basicalgos.blogspot.com/2012/03/14-find-element-in-sorted-matrix.html

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

``````i = 0;
while( a[i++][c-1] < x );
j = c-1;
while( a[i][j--] != x && j != 0 );
if( a[i][j] == x )
return Point(i,j);
else
return Point(-1,-1);``````

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

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] ?

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

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.

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

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

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

Here you are assuming that the matrix is nXn. Can you please help me as to how to do it if it is a mXn matrix where we cannot find diagonal elements?

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

How about using binary search diagonally and then linear search?

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

Iterate over rows and call binary search for each row.
Complexity : O(n log n)

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

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.

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

assume m rows and n columns (or vice versa)
assume m<n
iterate over m rows, performing binary search on each
which leads to m * log n complexity
O(mlogn)

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

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

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

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

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

People posting the diagonal traversal solutions. Please thing for a moment what if the matrix is not a perfect sqaure (m=n) and say the matrix is 10rows 2 columns. Yeap you are right, there does not exist a diagonal. Thank you

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

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

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

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

}

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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