23. Merge k Sorted Lists

It is a hard level algorithm. I wrote a minimum heap using SortedDictionary and also I shared my solution here.

I like to warm up this algorithm since I was asked to work on the algorithm back in August 2018 phone screen.

Here is the link.

It is hard level algorithm and also minimum heap is most popular data structure to work on. I learned to write the first minimum heap using SortedDictionary in August 2018, and it is time for me to warm up and study other C# solution as well.

I like to take some time to write a C# solution again.

Here are highlights:

1. Define MinHeap class using SortedDictionary, the key of dictionary is the value of linked list node's value, the value of dictionary is Queue;
2. Add two API for MinHeap class, one is to add node to the heap, second one is to remove minimum from heap. In order to find node with minimum value, since SortedDictionary is sorted, just call First() API and then get Key.
3. Time complexity is O(k * logk + n * logk), k is the heap size, n is total of nodes in all the lists.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _23_merge_k_sorted_lists
{
    class Program
    {
        public class ListNode {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }

        static void Main(string[] args)
        {
        }

        /// <summary>
        /// July 13, 2019
        /// I like to take the approach using minimum heap as a solution, so the time complexity will be O(N), 
        /// N is total of all nodes. 
        /// Assuming that lists's length is K, build a heap with size K, 
        /// time complexity: O(KlogN). 
        /// 
        /// </summary>
        /// <param name="lists"></param>
        /// <returns></returns>
        public ListNode MergeKLists(ListNode[] lists)
        {
            var heap = new MinHeap(); 

            // put head node in every list into minimum heap first
            foreach(var node in lists)
            {
                if (node == null)
                    continue;
                heap.Add(node.val, node);
            }

            // next build a linked list using ascending order
            ListNode current = null;
            ListNode newHead = null; 

            while(heap.map.Count > 0)
            {
                var node = heap.PopMin();
                if (node.next != null)
                    heap.Add(node.next.val, node.next);

                if (current == null)
                {
                    current = node;
                    newHead = current;
                }
                else
                {
                    current.next = node;
                    current = current.next; 
                }                
            }

            return newHead; 
        }

        /// <summary>
        /// Define my own minimum heap class MinHeap
        /// </summary>
        public class MinHeap
        {
            public SortedDictionary<int, Queue<ListNode>> map = new SortedDictionary<int, Queue<ListNode>>(); 

            public void Add(int val, ListNode node)
            {
                if(!map.ContainsKey(val))
                {
                    map.Add(val, new Queue<ListNode>());
                }

                map[val].Enqueue(node); 
            }

            public ListNode PopMin()
            {
                int minKey = map.First().Key;
                var node = map[minKey].Dequeue(); 

                if(map[minKey].Count == 0)
                {
                    map.Remove(minKey);
                }

                return node; 
            }
        }
    }
}