# Leetcode – 23. Merge k Sorted Lists

You are given an array of `k` arrays/linked-lists `arrays`, each array/linked-list is sorted in ascending or descending order.

Example 1:

```Input: arrays= [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
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.length`
• `0 <= k <= 10^4`
• `0 <= arrays[i].length <= 500`
• `-10^4 <= arrays[i][j] <= 10^4`
• `arrays[i]` is sorted in ascending / descending order.
• The sum of `arrays[i].length` won’t exceed `10^4`.

#### Solution

1. 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).
2. 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).
3. 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;
}

// 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.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] > arr[i][arr[i].Length - 1])
{
descending = true;
break;
}
}

int[] result = new int[arr.Length * arr.Length];

HeapNode[] hArr = new HeapNode[arr.Length];
for (int i = 0; i < arr.GetLength(0); i++)
{
hArr[i] = new HeapNode(arr[i], 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;
}``````