You are given an array of k arrays/linked-lists arrays, each array/linked-list is sorted in ascending or descending order.
Merge all the arrays/linked-lists into one sorted array/linked-list and return it.
Example 1:
Input: arrays= [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The arrays/linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted array/list: 1->1->2->3->4->4->5->6
Constraints:
k == arrays.length0 <= k <= 10^40 <= arrays[i].length <= 500-10^4 <= arrays[i][j] <= 10^4arrays[i]is sorted in ascending / descending order.- The sum of
arrays[i].lengthwon’t exceed10^4.
Solution
- If you use a brute force approach, then we need a large enough array to copy all elements from all arrays. Then sort the whole array. The time complexity would be O(NLogN) and Space complexity would be O(N).
- Another approach could be, to compare the first elements of all arrays and pick the smallest/highest among them. Delete it from the source array and put it in the first place of the result array. Repeat this process until you have a single element left. The time complexity would be O(kN) and Space complexity would be O(1).
- Optimize approach – using Priority Queue – Almost the same as approach 2 above but optimize the comparison process by a priority queue.
public class HeapNode
{
public int val; // The element to be stored
// index of the array from which the element is taken
public int r;
// index of the next element to be picked from array
public int c;
public HeapNode(int element, int i, int j)
{
this.val = element;
this.r = i;
this.c = j;
}
}
public class Heap
{
HeapNode[] harr; // Array of elements in heap
public bool IsMinHeap { get; private set; }
public int Count { get; private set; }
public void BuildHeap(HeapNode[] a)
{
for (int x = 0; x < a.Length; x++)
harr[x] = a[x];
Count = harr.Length;
// Index of last non-leaf node
int startIdx = (Count / 2) - 1;
// Perform reverse level order traversal
// from last non-leaf node and heapify
// each node
for (int i = startIdx; i >= 0; i--)
{
HeapifyDown(i);
}
}
public Heap(int size, bool _isMinHeap)
{
//??? is it max heap or Minheap
this.IsMinHeap = !_isMinHeap;
harr = new HeapNode[size];
}
void HeapifyUp(int i)
{
// check if node at index i and its parent violates
// the heap property
if (i > 0 && IsMinHeap && harr[parent(i)].val > harr[i].val)
{
// swap the two if heap property is violated
swap(i, parent(i));
// call Heapify-up on the parent
HeapifyUp(parent(i));
}
else if(i > 0 && !IsMinHeap && harr[parent(i)].val < harr[i].val)
{
// swap the two if heap property is violated
swap(i, parent(i));
// call Heapify-up on the parent
HeapifyUp(parent(i));
}
}
void HeapifyDown(int i)
{
// get left and right child of node at index i
int l = left(i);
int r = right(i);
if (IsMinHeap)
{
int smallest = i;
// compare A[i] with its left and right child
// and find smallest value
if (l < Count && harr[l].val < harr[i].val)
smallest = l;
if (r < Count && harr[r].val < harr[smallest].val)
smallest = r;
// swap with child having lesser value and
// call heapify-down on the child
if (smallest != i)
{
swap(i, smallest);
HeapifyDown(smallest);
}
}
else //max heap
{
int hightest = i;
// compare A[i] with its left and right child
// and find smallest value
if (l < Count && harr[l].val > harr[i].val)
hightest = l;
if (r < Count && harr[r].val > harr[hightest].val)
hightest = r;
// swap with child having lesser value and
// call heapify-down on the child
if (hightest != i)
{
swap(i, hightest);
HeapifyDown(hightest);
}
}
}
// to get index of left child of node at index i
int left(int i) { return (2 * i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2 * i + 2); }
int parent (int i) { return (i - 1) / 2; }
// to get the root
public HeapNode Top()
{
if (Count == 0)
throw new IndexOutOfRangeException("index is out of range(Heap underflow)");
return harr[0];
}
// A utility function to swap two min heap nodes
//void swap(List<MinHeapNode> arr, int i, int j)
void swap(int i, int j)
{
HeapNode temp = harr[i];
harr[i] = harr[j];
harr[j] = temp;
}
public int Pop()
{
// if heap has no elements, throw an exception
if (Count == 0)
throw new IndexOutOfRangeException("index is out of range(Heap underflow)");
int min = harr[0].val;
// replace the root of the heap with the last element of the vector
swap(0, Count - 1);
Count--;
// call heapify-down on root node
HeapifyDown(0);
return min;
}
public void Push(HeapNode item)
{
if(Count >= harr.Length)
throw new IndexOutOfRangeException("index is out of range(Heap underflow)");
// insert the new element to the end of the array
harr[Count] = item;
Count++;
// call heapify-up procedure on last element
HeapifyUp(Count - 1);
}
}
private static int[] MergeKSortedArray(int[][] arr)
{
bool descending = false;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i][0] > arr[i][arr[i].Length - 1])
{
descending = true;
break;
}
}
int[] result = new int[arr.Length * arr[0].Length];
HeapNode[] hArr = new HeapNode[arr.Length];
for (int i = 0; i < arr.GetLength(0); i++)
{
hArr[i] = new HeapNode(arr[i][0], i, 0);
}
//build the mean heap
Heap heap = new Heap(arr.Length, descending); //true - MinHeap, False - MaxHeap
heap.BuildHeap(hArr);
int r = 0;
while(heap.Count > 0)
{
HeapNode root = heap.Top();
result[r ++] = root.val;
heap.Pop();
//insert next item from same row
if ((root.c + 1) < arr[root.r].Length)
{
root.val = arr[root.r][root.c + 1];
root.c = root.c + 1;
heap.Push(root);
}
}
return result;
}