CC-18 : Merge K sorted arrays.

Description:

Given k sorted array of integers, merge the same. Sort order should be maintained in the merged array.

Test cases and expected outputs:

Input Parameters	Expected outputs
The Arrays : 11,32,93, 4,56,90, 5,51,94,	Merged & Sorted: 4,5,11,32,51,56,90,93,94

Pseudocode:

Class IntInfo:

Create an internal class IntInfo.

We will extract integers from input arrays and for each individual integer, the instances of IntInfo will hold reference to one integer and its row Index and column index with respect to input array of arrays.

Class SortNums:

This class implements Comparator.compare() method. The method takes 2 instance of IntInfo and helps to sort the same by magnitude of the integers.

Method sortKArrays(str):

This method takes k integer arrays named nums as parameter.

Initialize a PriorityQueue instance named minHeap. Provide an instance of SortNums to the constructor the PriorityQueue to sort by magnitude of the integers.

Iterate through rows (only) of input k arrays:

Create an instance of IntInfo and name it firstInt.

Set firstInt.iIdx to idx.

Set firstInt.jIdx to 0.

Set firstInt.num to nums[iIdx][jIDx].

Add firstInt to minheap.

Initialize a ArrayList instance named sorted to collate the sorted integers.

While heapsize is not 0:

Remove a IntInfo instance named minNum from top of heap.

Add minNum.Num to the heap.

Set i=minNum.iIdx.

Set j=minNum.jIdx.

if (j< nums[i].length-1):

Create an instance of IntInfo and name it nextInt.

Set nextInt.iIdx to i.

Set nextInt.jIdx to j+1.

Set nextInt.num to nums[i][j+1].

Add nextInt to minheap.

Return sorted.

Code:

public class HeapSortKArrays {

class IntInfo{
	int iIdx;
	int jIdx;
	int num;
}

class SortNums implements Comparator<IntInfo> {
	public int compare(IntInfo num1, IntInfo num2) {
		if (num1.num < num2.num) {return -1;}
		if (num1.num > num2.num) {return 1;}
		return 0;
	}	
}
 
public ArrayList<Integer> sortKArrays(int[][] nums) {
	
	ArrayList<Integer> sorted=new ArrayList<Integer>();
	PriorityQueue<IntInfo> minHeap=new PriorityQueue<IntInfo>(new SortNums());
	for (int idx=0; idx < nums.length; idx++) {
		IntInfo firstInt=new IntInfo();
		firstInt.iIdx=idx;
		firstInt.jIdx=0;
		firstInt.num=nums[idx][0];
		minHeap.add(firstInt);
	}
	while (minHeap.size() !=0) {
		IntInfo minNum=minHeap.remove();
		sorted.add(minNum.num);
		int i=minNum.iIdx;
		int j=minNum.jIdx;
		if (j < nums[i].length-1) {
			IntInfo nextInt=new IntInfo();
			nextInt.iIdx=i;
			nextInt.jIdx=j+1;
			nextInt.num=nums[i][j+1];
			minHeap.add(nextInt);
			
		}
	}
	return sorted;
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class HeapSortKArrays {

class IntInfo{
	int iIdx;
	int jIdx;
	int num;
}

class SortNums implements Comparator<IntInfo> {
	public int compare(IntInfo num1, IntInfo num2) {
		if (num1.num < num2.num) {return -1;}
		if (num1.num > num2.num) {return 1;}
		return 0;
	}	
}
 
public ArrayList<Integer> sortKArrays(int[][] nums) {
	
	ArrayList<Integer> sorted=new ArrayList<Integer>();
	PriorityQueue<IntInfo> minHeap=new PriorityQueue<IntInfo>(new SortNums());
	for (int idx=0; idx < nums.length; idx++) {
		IntInfo firstInt=new IntInfo();
		firstInt.iIdx=idx;
		firstInt.jIdx=0;
		firstInt.num=nums[idx][0];
		minHeap.add(firstInt);
	}
	while (minHeap.size() !=0) {
		IntInfo minNum=minHeap.remove();
		sorted.add(minNum.num);
		int i=minNum.iIdx;
		int j=minNum.jIdx;
		if (j < nums[i].length-1) {
			IntInfo nextInt=new IntInfo();
			nextInt.iIdx=i;
			nextInt.jIdx=j+1;
			nextInt.num=nums[i][j+1];
			minHeap.add(nextInt);
			
		}
	}
	return sorted;
}

public static void print2dArray(int[][] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
    // Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

public static void printArrayListSummary(ArrayList al, String label) throws Exception {
	if (al == null) { System.out.println("\n\n Input ArrayList was null !! \n"); return; }
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < al.size(); arrayIndex++) {
			System.out.print(al.get(arrayIndex));
			if (arrayIndex < al.size()-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}

public static void main(String[] args) {
	/************************
	 Test Cases given below
	 **********************/
	ArrayList<Integer> retVal;
	try {
	HeapSortKArrays hp=new HeapSortKArrays();
	int[][] nums= {{11,32,93}, {4, 56, 90}, {5, 51, 94}};
	print2dArray(nums, "The Arrays");
	retVal=hp.sortKArrays(nums);
	printArrayListSummary(retVal, "Sorted: ");
	
	
		
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}