Saturday, November 5, 2016

Merge k sorted arrays

Problem
Given k sorted arrays of size n each, merge them and print the sorted output.

Solutions
This problem can be solved in multiple ways.
- Take first two arrays and merge those. Now the rest all arrays with the merge result one by one.
- We can use the min heap of size 'k'. Add one element from each array and remove smaller element from heap. Once the smaller element is removed, from the same array insert next element in to heap. This way remove all the elements from heap and put in to merge array.
- Lastly instead of maintaining heap, we can just compare one element from each array, compare min from those and add to merge result. Now take next element from same array. Follow this till all elements are sorted. Solution below implements this approach.
import java.util.ArrayList;
import java.util.List;

public class MergeKSortedArrays {
    public static void MergeSortedArrays(int[][] sortedArrays) {
        int maxSize = sortedArrays.length * sortedArrays[0].length;

        int[] mergedArray = new int[maxSize];

        List arrayIndices =  new ArrayList<>();
        for (int[] sortedArray : sortedArrays) arrayIndices.add(0);

        for (int i = 0; i < maxSize; i++){
            int minSoFar = Integer.MAX_VALUE;
            int minIndex = 0;

            for(int index = 0; index < arrayIndices.size(); index++){
                if ( sortedArrays[index].length > arrayIndices.get(index) && sortedArrays[index][arrayIndices.get(index)] < minSoFar){
                    minSoFar = sortedArrays[index][arrayIndices.get(index)];
                    minIndex = index;
                }
            }
            mergedArray[i] = sortedArrays[minIndex][arrayIndices.get(minIndex)];
            arrayIndices.set(minIndex, arrayIndices.get(minIndex) + 1);
        }

        System.out.println("Merged : ");
        for (int i : mergedArray){
            System.out.print( i + ", ");
        }
    }

    public static void main(String[] args) {

        int[][] A = new int[5][];

        A[0] = new int[] { 1, 5, 8, 9 };
        A[1] = new int[] { 2, 3, 7, 10 };
        A[2] = new int[] { 4, 6, 11, 15 };
        A[3] = new int[] { 9, 14, 16, 19 };
        A[4] = new int[] { 2, 4, 6, 9 };

        MergeSortedArrays(A);
    }
}

Comments are welcome.

No comments:

Post a Comment