...

/

Solution: Merge a Number of Sorted Arrays

Solution: Merge a Number of Sorted Arrays

This review discusses the solution of the merge sorted arrays challenge in detail.

Solution#1

Press + to interact
class Merge {
public static int n = 4;
public static ArrayList < Integer > mergeSortedArrays(int[][] arr, ArrayList < Integer > Output) {
//traversing the 2-D array and appending all arrays into an ArrayList
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
//adding into the ArrayList
Output.add(arr[i][j]);
}
}
//sorting the ArryList using the inbuilt sort function
Collections.sort(Output);
return Output;
}
public static void main(String args[]) {
// 2D input array
int[][] arr = {{16, 25, 36}, {2, 9, 15}, {22, 55, 67}, {79, 38, 99}};
ArrayList < Integer > Output = new ArrayList < Integer > ();
System.out.print(mergeSortedArrays(arr, Output));
}
}

A naive solution to this problem would be:

  1. Append all the arrays one after another in an ArrayList say Output.
  2. Next, simply sort the Output using the built-in Java function, i.e., Collections.sort();.

Time complexity

Appending kk sorted arrays into an ArrayList array would take O(nk)O(n*k) time. Since Collections.sort() runs in O(sizelog(size))O(size*log(size)) and the size of Output is (nk)(n*k) ...