Solution: Merge a Number of Sorted Arrays
This review discusses the solution of the merge sorted arrays challenge in detail.
We'll cover the following...
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 ArrayListfor (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[i].length; j++) {//adding into the ArrayListOutput.add(arr[i][j]);}}//sorting the ArryList using the inbuilt sort functionCollections.sort(Output);return Output;}public static void main(String args[]) {// 2D input arrayint[][] 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:
- Append all the arrays one after another in an ArrayList say
Output
. - Next, simply sort the
Output
using the built-in Java function, i.e.,Collections.sort();
.
Time complexity
Appending sorted arrays into an ArrayList array would take time. Since Collections.sort()
runs in and the size of Output
is ...