CareerCup

we can use n-way merge using minimum heap of size(min of no of row and coloumn ) ,
it 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

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.

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.

You can use a set. Set does not allow duplicates. Put all the elements in the set. Then remove and do quicksort.

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.

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

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.

I think we can use Binary Search Tree to store unique values of 2D array in sorted manner. STL set can also be used.

You can use TOURNAMENT tree.

Time: O(N*M*lgM)
Space: O(2M-1) ~ O(M)

This can be done using merge. foreach row i in Arr Merge row(i) to row(i+1). While merging, make sure to drop the number if its duplicate.

Merging will take O(n) because rows are sorted. Merging m rows will take O(m).
Total complexity time O(n*m). Space complexity O(m+n).

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