Leetcode discuss: 632. Smallest Range Covering Elements from K Lists

June 30, 2022

Here is the link. 

C# | Quick learner | Heap - Max and Min

June 30, 2022
Introduction
It is a hard level algorithm. What I did is to think about 5 minutes, and spent 5 minutes to read top-voted discuss post, and then moved on C# discuss post, studied and wrote my own. I like to cut short time to review and warmup hard level algorithms.

Hard level algorithms | My approach

1944	Number of Visible People in a Queue

428	Serialize and Deserialize N-ary Tree

1096	Brace Expansion II

847	Shortest Path Visiting All Nodes

1597	Build Binary Expression Tree From Infix Expression

I spent three hours to go over 5 hard levle algorithms yesterday, and I only solved 847. Definitely I learned a few things. I have no clue what I learned yesterday about other 4 algorithms. But I am thinking about the new approach. Since I am approaching 700 algorithms solved, I have a lot of experience already. I try three 5-minutes approach.

Three 5-minutes approach on hard level algorithm

1. Think about 5 minutes by myself - idea, design, and things to look into
2. 5 minutes top voted discuss post - read some ideas shared by top-voted discuss post - Cut time short if needed, 5 minutes only
3. Study one C# discuss post - 5 minutes
4. Work on C# code rewrtie - Learn by doing.

Time complexity:
O((klogk)kL, k is total rows, L is total columns

The following C# code passes online judge.

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

namespace _632_smallest_range
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = new List<IList<int>>();
            list.Add(new int[] { 4, 10, 15, 24, 26 }.ToList());
            list.Add(new int[] { 0, 9, 12, 20 }.ToList());
            list.Add(new int[] { 5, 18, 22, 30 }.ToList());

            var result = SmallestRange(list);
        }

        /// <summary>
        /// 1. 5 minutes to read top-voted discussion post
        /// 2. study code
        /// https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/discuss/1790188/Elegant-implementation-with-C-SortedSet-or-M-Log(min(len(M)))         
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int[] SmallestRange(IList<IList<int>> nums) {
            var rows = nums.Count;
            var columns = nums[0].Count;
        
            // Tuple<int, int, int> design: value, row, column
            var heap = new SortedSet<Tuple<int, int, int>>();
        
            for(int row = 0; row < rows; row++)
            {
                heap.Add(new Tuple<int, int, int>(nums[row][0], row, 0));
            }
			
            var rangeMin = 0;
            var rangeMax = int.MaxValue;
        
            while(heap.Count > 0)
            {
                var min = heap.Min;
                var max = heap.Max;

                if(rangeMax - rangeMin > max.Item1 - min.Item1)
                {
                    rangeMin = min.Item1;
                    rangeMax = max.Item1;
                }

                heap.Remove(min);

                var nextRow = min.Item2;
                var nextColumn = min.Item3 + 1;

                if(nextColumn == nums[nextRow].Count)
                {
                    return new int[] {rangeMin, rangeMax};
                }            
                
                heap.Add(new Tuple<int, int, int>(nums[nextRow][nextColumn], nextRow, nextColumn));
            }

            return new int[0];
        }
    }
}