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.

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.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[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;
}