## Amazon Interview Question

**Country:**United States

So let's do a dryrun for min heap approach:

a. Insert from the first row {2 5 7 9 14 16} first in the heap.

b. At this point the root node of the heap contains element 2.

c. Start inserting from second node {3 6 8 10 15 21}.So let's pick the first element of the second node which is 3.So we will check if 2<3 and it is so we will just add the 3 in the leaf node of the heap.

'C' step will be repeated for all the rest of the nodes in the row 2.

This whole thing will end once we have accounted for all the rows in the heap.

I wonder how will we take care of repeats?

I think you want to insert 2 3 4 7 into the min heap

when you process the heap, remove the root, which is 2,

add the second number in the first row into the heap, which is 5.

you need to keep a pointer for each row where all numbers before the pointer are already added into the heap.

@anish1 ...this will work for repetition also and yang is not processing columnwise this is how you will have to create the heap picking 1st element from each row(starting with it) and then pick next element from row whose element has been recently popped from the min heap.

@zerobyzero ... ur logic is correct however your step 3(simply increment its pointer in the repected row) will be able to avoid adding repeated element to heap only if the repeated item is being brought into heap after pop or in other words the next smallest element is being inserted in heap which is same as popped element. However if the repeated elements were brought into heap from diff rows and they were not smallest at that time then they will be inserted in heap....Anyway it will work in that case also as you can always have repetition in min heap with a tie breaker

If memory is abundant, I think this can be done in O(m * n) time. The solutions shown up to this point are actually O((m * n) lg(m * n))

1. Find the biggest element k in the array. Time: O(m * n)

2. Create a 1D array Z of size k and set each value to zero. Time: O(m * n)

3. Insert every element into the array at the index equal to its value. This is basically a dummy hash table. For instance, 5 would go into Z[5]. Time: O(m * n)

4. Create a linked list L and set the head node of L equal to the smallest element in the array. Time: O(m) -> you can find it by iterating the first column

5. Now that the elements are sorted (other than the zeroes), iterate through array Z, inserting the values onto the end of the linked list L. Time: O(m * n)

6. Create an array R the size of the L and fill the array with the contents of L. Time: O(m * n)

7. Return R

Time: O(5 * m * n + m) = O(m * n)

Space: Constant (but could be quite large). Again, this solution emphasizes an vastly improved worst case time over optimizing space.

Cant largest element be found by only traversing last column...then its not o(m*n)...Am i missing somethin?

You need a hash table. Iterate through the matrix, and put the element in the hashtable if it is not in the hash and then put it in the new array. If the element is in the hashtable, skip the element and move on to the next one in the 2d matrix. Once you have gotten the unique elements from the matrix, use quicksort. O(nlgn) time complexity algo.

we can make a heap-tree from the given elements as heap tree is a balanced-Binary tree so height is propotional to logn so building up heap-tree from n-unique elements will take O(nlogn)time,then we can use heap-sort to sort in O(nlogn) time.This will save extra use of HashTable.

All we need is a binary tree, it should be faster to insert the elements and it provides a sorted set as a result.

Since each of the m rows are sorted, all you need to do is to do a m-way comparison to find the minimum element from the m rows. You can ignore duplicates since you know the previous minimum. This will give an O(mn*m) algorithm since there are m comparisons at each step.

However, the m-way comparison at each step to find the minimum can be done using a heap - which will give us an O(mn*logm) algorigm with only O(m) extra memory.

Here is the code:

```
class mycomparison
{
public:
bool operator() (const pair<int,int> & lhs,
const pair<int,int> & rhs)
{
return lhs.first > rhs.first;
}
};
vector<int> MergeMatrix(int input[M][N])
{
priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pq;
vector<int> result;
vector<int> current(M, 0);
for (int i=0; i < M; i++)
{
pair<int,int> value;
value.first = input[i][0];
value.second = i;
pq.push(value);
current[i]=0;
}
while (! pq.empty() )
{
pair<int,int> top;
top = pq.top();
pq.pop();
if (result.size() ==0)
{
result.push_back(top.first);
}
else if (result[result.size()-1] != top.first)
{
result.push_back(top.first);
}
if (current[top.second] < N-1)
{
current[top.second]++;
top.first = input[top.second][current[top.second]];
pq.push(top);
}
}
return result;
}
```

This can be done in O(m * n) time using only arrays:

```
public static int[] MergeAndSort(int[][] inputArray){
int m = inputArray.length;
int n = inputArray[0].length;
int high = Integer.MIN_VALUE;
int low = Integer.MAX_VALUE;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (inputArray[i][j] > high)
high = inputArray[i][j];
if (inputArray[i][j] < low)
low = inputArray[i][j];
}
}
int[] hash = new int[high-low + 1];
int counter = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (hash[inputArray[i][j] - low] == 0)
counter++;
hash[inputArray[i][j] - low] = 1;
}
}
int[] newOne = new int[counter];
int count = 0;
for (int i = low; i < high+1; i++)
if (hash[i - low] == 1)
newOne[count++] = i;
return newOne;
}
```

further optimization

u don't need to traverse the whole 2D array to find the min and max elements . Since the row are sorted , just need to compare the first and last elements of all rows to find min and max.

Basically you are doing COUNTING SORT.

In this case: offset = hight- low + 1

Time and space in worst case: O(N*M + offset)

Hello, my friend ,assume we have two rows, each row contains one element.

Row 1 : 1

Row 2: 2^31 -1

your algorithm is gonna be really bad in this situation

The approach should be similar to the one used in merge sort to merge the sorted parts. The only difference is here we have m parts comparing to the 2 parts in standard merge sort. Here is the Java implementation

```
import java.util.Arrays;
public class Merge {
public int[] mergeAndSort(int[][] matrix) {
if (matrix == null) {
return null;
}
int[] result = new int[matrix.length * matrix[0].length]; //assuming n is fixed, otherwise it can be calculated
int[] rowsIndexes = new int[matrix.length];
int arrayIndex = 0;
int currentCount = 0;
int max = getMax(matrix);
while (currentCount++ < result.length) {
int min = getNextMatrixMin(matrix, rowsIndexes, max);
if (arrayIndex == 0 || min > result[arrayIndex-1]) {
result[arrayIndex++] = min;
}
}
return trim(result, arrayIndex);
}
private int[] trim(int[] array, int toSize) {
int[] trimmed = new int[toSize];
for (int i = 0; i < toSize; i++) {
trimmed[i] = array[i];
}
return trimmed;
}
private int getMax(int[][] matrix) {
int max = matrix[0][matrix[0].length - 1]; //last element in the first row
//check if the any last element in other rows is bigger
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][matrix[i].length - 1] > max) {
max = matrix[i][matrix[i].length - 1];
}
}
return max;
}
private int getNextMatrixMin(int[][] matrix, int[] rowsIndexes, int max) {
int min = max;
int index = 0;
for (int i = 0; i < matrix.length; i++) {
if (rowsIndexes[i] < matrix[i].length && matrix[i][rowsIndexes[i]] < min) {
min = matrix[i][rowsIndexes[i]];
index = i;
}
}
rowsIndexes[index]++;
return min;
}
public static void main(String[] args) {
int matrix[][] = {
{2, 5, 7, 9, 14, 16},
{3, 6, 8, 10, 15, 21},
{4, 7, 9, 15, 22, 35},
{7, 8, 9, 22, 40, 58}
};
int[] array = new Merge().mergeAndSort(matrix);
System.out.println(Arrays.toString(array));
}
}
```

In python:

```
def sort2darr(arr):
mpos = [1]*len(arr[0])
heap = [(x[0],i) for (i,x) in enumerate(arr)]
heapq.heapify(heap)
(val, idx) = heapq.heappop(heap)
res = [val]
mpos[idx] += 1
while True:
try:
(val, idx) = heapq.heappop(heap)
except IndexError:
return res # done
if val != res[-1]:
res.append(val)
if mpos[idx] < len(arr[0]):
to_push = (arr[idx][mpos[idx]], idx)
heapq.heappush(heap, to_push)
mpos[idx] += 1
```

The idea is to maintain a heap of the smallest item in each row, advancing the indexes.

Jerry.

Here is a little piece of code from me:

```
import java.util.Arrays;
public class SortedMatrixToSortedArray {
public static void main(String... args) {
int[][] matrix = {
{2, 5, 7, 9, 14, 16},
{3, 6, 8, 10, 15, 21},
{4, 7, 9, 15, 22, 35},
{7, 8, 9, 22, 40, 58}
};
int[] result = mergeAndSort(matrix);
int[] expected = {2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35,
40, 58};
System.out.printf("result: %s%n", Arrays.toString(result));
System.out.printf("expected: %s%n", Arrays.toString(expected));
}
private static int[] mergeAndSort(int[][] matrix) {
int[] result = new int[]{};
for (int[] row : matrix) {
result = mergeAndSort(result, row);
}
return result;
}
private static int[] mergeAndSort(int[] x, int[] y) {
int n = findDistinctLength(x, y);
int[] result = new int[n];
for (int k = 0, i = 0, j = 0; k < n; k++) {
if (i == x.length) {
result[k] = y[j++];
} else if (j == y.length) {
result[k] = x[i++];
} else if (x[i] < y[j]) {
result[k] = x[i++];
} else if (x[i] > y[j]) {
result[k] = y[j++];
} else {
result[k] = x[i];
i++;
j++;
}
}
return result;
}
private static int findDistinctLength(int[] x, int[] y) {
int i = 0;
int j = 0;
int n = 0;
while (i < x.length && j < y.length) {
if (x[i] < y[j]) {
i++;
} else if (x[i] > y[j]) {
j++;
} else {
i++;
j++;
}
n++;
}
return n + x.length - i + y.length - j;
}
}
```

See with tests here - github.com/ffbit/just-for-fun/blob/master/src/test/java/com/ffbit/fun/array/SortedMatrixToSortedArray.java

The problem can be solved using binary search tree / merge sort

An alternate way of solving this problem,

1. Created an 1-D array

2. Since each row is sorted, start reading data from first column of each row, and store into 1-D. Starting from row 0 to r - 1.

3. Record the tail index of the 1D array.

4. While storing the data, looks from backwards of 1-D array to find an slot for the new element / discard duplicate.

5. Shift the elements towards right, when new elements are not added towards the end of 1D array.

6. Step 2 is repeated till last column

1st method: merge sort

take two rows at a time and merge adding check for repetitions. This will require maintaining two arrays of size m*n and need to switch between them. T(m*n) S(m*n) however constants and space requirements are high.

2nd method: maintain a min-heap

maintain 2 arrays of size m. one will store the row index of elements in a min heap and other the corresponding column index. solution can be devised in following 3 steps:

1) Initialize a min Heap.

2) Make a min Heap

3) Pop elements and store in resultant array.

Below code gives an idea.

```
int main()
{
int arr[m][n],hashRow[m],minArr[m],resArr[m*n],i,j;
i=0;
1st step
while(i<m)
{
j=0;
while(j<n)
{
if(!isUnique(minArr,arr[i][j])) //---------T(m)
j++;
else
{
minArr[index]=i;
hashRow[i]=j;
index++;
break;
}
}
}
// 2nd step
makeMinHeap(minArr,hashRow,index-1); //--------------T(mlogm)
//3rd step
while(index>=0)
{
resArr[count++]=minArr[0];
i=minArr[0];
j=resArr[i]+1;
while(j<n)
{
if(!isUnique(minArr,arr[i][j]))
j++;
else
{
minArr[0]=arr[i][j];
hashRow[i]=j;
break;
}
}
if(j=n)
{
minArr[0]=minArr[index];
index--;
}
restoreDown(minArr,index,0); //-------------------T(m*nlogm)
}
}
```

```
#include<stdio.h>
#include<stdlib.h>
int B[100];
int j=0;
void smallest(int *p[],int n, int r, int *counter)
{
int i;int min=*p[r];
for(i=r+1;i<n;i++)
{
if(*(p[i])<min)
{
min=*p[i];
break;
}
}
for(i=0;i<n;i++)
{
if(min==*p[i])
{
p[i]++;
counter[i]++;
}
}
B[j++]=min;
}
int main()
{
int x[4][6]={{2,5,7,9,14,16},
{3,6,8,10,15,21},
{4,7,9,15,22,35},
{7,8,9,22,40,58}};
int m=4;//number of rows
int n=6;//number of columns
int *p[4]={x[0],x[1],x[2],x[3]};//array of pointer storing each rows
int i,k=1;
int counter[4];
int r=0;
for(i=0;i<m;i++)
counter[i]=0;
while(k<m*n)
{
if(*p[r]==x[m-1][n-1])
break;
if(counter[r]==n)
r++;
smallest(p,m,r,counter);
k++;
}
B[j++]=x[m-1][n-1];
for(i=0;i<j;i++)
printf("%d\n",B[i]);
//
}
```

we can use n-way merge using minimum heap of size(min of no of row and coloumn ) ,

- zeroByzero January 08, 2013it is example of standard n-way merge , here we are given n-sorted rows in 2-D matrx .

algorithm would work like :

1. pick up 1st elements from all the rows and insert them into Min-heap.

2. top of element contain minimum element , pop it and insert element from the array

whose element was poped .

3. while making insertion check the last popped value , if it is same then do not push this into heap, simply increment its pointer in the repected row, this will take care of duplicates too.

3.keep doing this operation till no element is left in any of the row and heap .

Complexity: if matrix is of size m*n

O(log m)*m*n