Merge k Sorted Arrays


  • 0
    S

    Input is k sorted arrays in the form of a 2D matrix (int[][] int Java). Output should be a single sorted array in the form of either array or ArrayList.


  • 1
    O

    This solution will assume all arrays are of the same size, it could be modified to accept a list of arrays which size is not necessarily the same.
    this implementation will keep duplicated items, it could be modified to remove duplicated items.

    for each array it will add the elements on an ordered list, then the list is turned into an array

    I added a simple test to validate the algorithm

    using Microsoft.VisualStudio.TestTools.UnitTesting;
    
    namespace AlgorithmsTests
    {
        [TestClass]
        public class MergeKSortedArrays
        {
            [TestMethod]
            public void MergeKSortedArrays_Test()
            {
                //define the arrays
                int[][] arr = new int[][]
                    {
                        new int[] { 2, 5 ,8 ,12},
                        new int[] { 4, 9 ,22, 23},
                        new int[] { 2, 105, 106,1000}
                    };
    
                Assert.IsTrue(AreArraysEqual(
                    new int[] { 2, 2, 4, 5, 8, 9, 12, 22, 23, 105, 106, 1000 },
                    MergeArrays(arr)));
            }
    
            //add them into an ordered linked list
            private int[] MergeArrays(int[][] arr)
            {
                if (arr == null)
                {
                    return null;
                }
    
                OrderedLinked list = new OrderedLinked();
                for (int i = 0; i < arr.Length; i++)
                    for (int j = 0; j < arr[i].Length; j++)
                    {
                        list.Add(arr[i][j]);
                    }
    
                return list.ToArray();
            }
    
            //compare each item on the array ( for validation)
            private bool AreArraysEqual(int[] a, int[] b)
            {
                if (a.Length != b.Length)
                    return false;
                for (int i = 0; i < a.Length; i++)
                {
                    if (a[i] != b[i])
                    {
                        return false;
                    }
                }
                return true;
            }
    
            class OrderedLinked
            {
                LinkedListNodeImp Head;
                private int size = 0;
                public void Add(int value)
                {
                    LinkedListNodeImp p = Head;
                    LinkedListNodeImp prev = null;
                    LinkedListNodeImp c = new LinkedListNodeImp() { Value = value };
                    while (p != null && p.Value < value)
                    {
                        prev = p;
                        p = p.Next;
                    }
                    if (prev != null)
                    {
                        //not the first element inserti it
                        prev.Next = c;
                    }
                    else
                    {
                        //first element, add it to the head
                        Head = c;
                    }
                    c.Next = p;
                    //keep track of the size for later
                    size++;
                }
    
                public int[] ToArray()
                {
                    int[] arr = new int[size];
    
                    // add each one in order to the new array
                    LinkedListNodeImp p = Head;
                    int i = 0;
                    while (p != null)
                    {
                        arr[i++] = p.Value;
                        p = p.Next;
                    }
                    return arr;
                }
            }
    
            class LinkedListNodeImp
            {
                public int Value;
                public LinkedListNodeImp Next;
            }
        }
    }
    

  • 3

    Minheap can be used to store the k top elements. Extract min element from the heap and then replace it by a next element of an array whose element was minimum last time. Then Heapify it. Do this for all the elements.
    Time Complexity: O(nlog(k))


  • 1
    N

    If you convert 2D list to 1d list and apply mergeSort it will print sorted 1D list, time complexity : O(n log n)

    #Typical Merge Sort 
    def mergeSort(mlist):    
        result = []
        mlen = len(mlist)
        if mlen < 2:
            return mlist
        
        # split until left and right are single element list    
        mid = mlen // 2
        l = mergeSort(mlist[:mid])
        r = mergeSort(mlist[mid:])
        
        i = 0
        j = 0
        
        while i < len(l) and j < len(r):    
            if l[i] > r[j]:
                result.append(r[j])
                j += 1
            else:
                result.append(l[i])
                i += 1
                
        result += l[i:]
        result += r[j:]
        
        return result
    
    
    d = [
      [1,3,2,5],
      [9,8,3],
      [4,9,11,6,1]
    ]
    argList = []
    for di in d:
        argList += di
    	
    ans = mergeSort(argList)
    print(ans)
    

  • 0
    U

    it seems this code is more easy to understand. column is an array to save the position of every row index.

    static List<Integer> mergeKSortedArray(int[][] arr) {
    		List<Integer> res = new ArrayList<>(arr.length * arr[0].length);
    		int[] column = new int[arr.length];
    		
    		boolean changed = true;
    		while(changed) {
    			changed = false;
    			int min = Integer.MAX_VALUE;
    			int minRow = -1;
    			for (int i = 0; i < arr.length; i++) {
    				if (column[i] < arr[i].length && arr[i][column[i]] < min) {
    					min = arr[i][column[i]];
    					minRow = i;
    					changed = true;
    				}
    			}
    			if (changed) {
    				res.add(min);
    				column[minRow]++;
    			}
    		}
    		
    		return res;
    	}
    

  • 0
    D

    I think flatten out the 2D matrix and sort it is a better solution than using Min Heap or Priority Queue.

    O(NlogN) vs O(Nlogk) is not a big difference, but the implementation is much simpler

    log2(10_000_000) = 23 vs. log2(10) = 3

    Very simple implementation in Ruby

    a.flatten.sort
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.