Kth Smallest Number in M Sorted Lists using MinHeap<T> and custom IComparable class ElementArrayIndexPair

gistfile1.txt

/*

Kth Smallest Number in M Sorted Lists:
Given ‘M’ sorted arrays, find the K’th smallest number among all the arrays.

Example:

Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4], K=5
Output: 4

Naive Approach:
// Dump all elements into a list
// Sort the list
// Return index[k-1]
// tO(N log N)
// sO(N)

Next Approach:
// Push all lists into maxHeap
// Maintain maxHeap size of K by only pushing in elements that are less than the root of maxheap
// Give root at end
//tO(N log K + k Log k) => tO(N log K)
//sO(K)

Best Approach:
// Initialize first element from each list into a MinHeap
// We insert K more additional items from M sorted arrays until the count of total elements inserted reaches K
//     To do this, we keep track of the array and element indices using a new class called ElementArrayPair
// tO(MlogM + K logM) => tO(K logM)
// sO(M)

*/

using System;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        int[] l1 = new int[] {1,2,3};
        int[] l2 = new int[] {4,5,6};
        int[] l3 = new int[] {7,8,9};
        
        List<int[]> lists = new List<int[]>();
        lists.Add(l1);
        lists.Add(l2);
        lists.Add(l3);
        
        Console.WriteLine(FindKSmallestAmongMLists(lists,6));
    }
    
    public class ElementArrayPair : IComparable<ElementArrayPair>
    {
        public int ElementIndex {get; set;}
        public int ArrayIndex {get; set;}
        public List<int[]> Lists {get; set;}
        
        public ElementArrayPair(List<int[]> lists, int eIndex, int aIndex)
        {
            Lists = lists;
            ElementIndex = eIndex;
            ArrayIndex = aIndex;
        }
        
        public int CompareTo(ElementArrayPair otherPair)
        {
            if (otherPair == null)
            {
                return 1;
            }

            return this.Lists[ArrayIndex][ElementIndex].CompareTo(otherPair.Lists[otherPair.ArrayIndex][otherPair.ElementIndex]);
            
        }
    }
    
    public static int FindKSmallestAmongMLists(List<int[]> lists, int k)
    {
        MinHeap<ElementArrayPair> minHeap = new MinHeap<ElementArrayPair>();
            
        for (int i = 0; i < lists.Count; i++)
        {
            if(lists[i] != null)
            {
                minHeap.Push(new ElementArrayPair(lists, 0, i));
            }
        }
        
        int numberCount = 0;
        int result = 0;
        
        while (minHeap.Count > 0)
        {
            ElementArrayPair pair = minHeap.Pop();
            result = lists[pair.ArrayIndex][pair.ElementIndex];
            if (++numberCount == k)
            {
                break;
            }
            pair.ElementIndex++;
            if(lists[pair.ArrayIndex].Length > pair.ElementIndex)
            {
                minHeap.Push(pair);
            }
        }
        
        return result;
    }
    
    public class MinHeap<T> where T: System.IComparable<T> 
    {
        public List<T> heapList {get; set;}

        public int Count {get => heapList.Count;}

        private int GetLeftChildIndex(int elementIndex) => 2 * elementIndex + 1;
        private int GetRightChildIndex(int elementIndex) => 2 * elementIndex + 2;
        private int GetParentIndex(int elementIndex) => (elementIndex - 1) / 2;

        private bool HasLeftChild(int elementIndex) => GetLeftChildIndex(elementIndex) < Count;
        private bool HasRightChild(int elementIndex) => GetRightChildIndex(elementIndex) < Count;
        private bool IsRoot(int elementIndex) => elementIndex == 0;

        private T GetLeftChild(int elementIndex) => heapList[GetLeftChildIndex(elementIndex)];
        private T GetRightChild(int elementIndex) => heapList[GetRightChildIndex(elementIndex)];
        private T GetParent(int elementIndex) => heapList[GetParentIndex(elementIndex)];

        public MinHeap()
        {
            heapList = new List<T>();
        }

        public void PrintHeap()
        {
            foreach (T item in heapList)
            {
                Console.WriteLine(item.ToString());
            }
        }

        public void Push (T item)
        {
            heapList.Add(item);
            BubbleUp(Count - 1);
        }

        public T Pop ()
        {

            if (Count == 0)
            {
               throw new IndexOutOfRangeException();
            }

            // store copy to return at the end of the method
            T firstItemCopy = heapList[0];

            // move last item to first position
            heapList[0] = heapList[Count - 1];

            // remove the last thing off the list because it's redundant (it's now at the top of the heap)
            heapList.RemoveAt(Count - 1);

            FilterDown(0);

            return firstItemCopy;
        }

        public T Peek()
        {
            if (Count == 0)
            {
               throw new IndexOutOfRangeException();
            }

            return heapList[0];
        }

        public bool IsEmpty()
        {
            return Count == 0;
        }

        void Swap (int firstIndex, int secondIndex)
        {
            T temp = heapList[firstIndex];
            heapList[firstIndex] = heapList[secondIndex];
            heapList[secondIndex] = temp;
        }

        void BubbleUp (int index)
        {
            while (!IsRoot(index) && heapList[index].CompareTo(GetParent(index)) < 0)
            {
                int parentIndex = GetParentIndex(index);

                Swap(parentIndex, index);

                index = parentIndex;
            }
        }

        void FilterDown (int index)
        {
            // set currentIndex
            int currentIndex = index;

            // while loop: check if index has a left child
            while (HasLeftChild(currentIndex))
            {
                // if it does, establish a smaller index
                int smallerIndex = GetLeftChildIndex(currentIndex);

                // check and see which of the left or right child has a smaller value
                // allocate the smaller value child as the smaller index
                if (HasRightChild(currentIndex) && GetRightChild(currentIndex).CompareTo(GetLeftChild(currentIndex)) < 0)
                {
                    smallerIndex = GetRightChildIndex(currentIndex);
                }

                // if the element at smallerindex is bigger than the element at current index, then break
                if (heapList[smallerIndex].CompareTo(heapList[currentIndex]) >= 0)
                {
                    break;
                }

                // otherwise, swap element[currentindex] with element[smallerindex]
                Swap(smallerIndex, currentIndex);

                // set index to smallerIndex
                currentIndex = smallerIndex;

                // while loop will break when the index no longer has a left child
            }
        }
    }
}