Leetcode discuss: 1631. Path With Minimum Effort

Here is the link on youtube.com. 

Here is my Leetcode discuss post.

First practice - C# copy idea and copy code to learn quickly

Oct. 25, 2020
Introduction
It is the third algorithm in weekly contest 212. I started the contest late and only had 10 minutes left, I thought about the problem and it was hard. I could not find a working idea.

After the contest
I just quickly went over the discussion post, and then I like to study the code and then figure out the following:

1. Start from top left node in the matrix, define C# Tuple<int, int,int>(int Height, int row, int col);
2. Try to start from top left node to visit all nodes in the matrix, but choose the order to get minimum distance. How to do that? Design a minimum heap.
3. Define a minimum heap with distance, and always remove the minimum node from the heap, and then visit it's unvisited neighbors, and add all those neighbors to the heap.
4. Make sure that visit all nodes in the order based on minimum distance until bottom right node is reached.
5. Define a node with distance based on consideration of previous node's distance in minimum heap process and current one.

Case study
I think that the code is pretty standard minimum heap practice once I understand the idea and learn how to reason it.

I need to look into C# SortedSet default comparer for this Tuple<int, int, int>. It is surprising that the code can be simplified using short hand expression, and no need to write any code related to IComparer as well. I did look up Google.

It is much better to work on a small case study, then I can quickly understand the algorithm and how to design it next time.

Example:
Matrix
1, 2, 3
3, 8, 2
5, 3, 5
Using A, B, C, D, E to mark those first five nodes in matrix.
1A, 2B, 3C
3D, 8E, 2
5, 3, 5
Add A node in matrix into minimum heap, (0,0,0), remove minimum one in the heap, and then visit A's neighbor nodes B and D, and then add B and D into minimum heap.
Next step is to remove minimum node in the heap, which is B. The distance is 1, and add C and E into the heap.

Step by step
Let me work on a more simple example,
Example:
Matrix
1, 2
3, 8
Add A, B, C, D marks to simplify the explanation.
1A, 2B
3C, 8D
1A is added to minimum heap, the minimum effort is 0;
remove 1A from minimum heap, and visit two neighbors, 2B and 3C.
1A -> 2B has minimum effort 1, and 1A to 3C has minimum effort 2.

Add 2B and 3C to minimum heap. The smallest one is 2B.

Next is to remove 3B from minimum heap, visit 2B's neighbor 8D, so 8D has minimum effort 6. Add (6, 1, 1) to minimum heap.

Next is to remove 3C from minimum heap, visit 3C's neighbor 8D, so 8D has minimum effort 5. Add (5, 1, 1) to minimum heap.

The tip is to mark visit only after the node is popped from minimum heap. In our simple example case, 8D has chance to be added into minimum heap more than once, first one is with height 6, second one is with height 5.

Since minimum heap is sorted, the path from 1A->3C->8D is removed from minimum heap first before 1A->2B->8D, the answer is 5 not 6.

In summary, the first tip is enforce order using minimum heap, and the second tip is to mark visit after the node is removed from minimum heap, so one node 8D has two chance to be considered and added to minimum heap. It is kind of clever. But it took me over 30 minutes to figure out, I had to debug the code using Visual studo first, and then figure out step by step.

Go over again, the minimum heap step by step:

1. 1A, (0, 0, 0)
2. remove 1A from heap, add 2B and 3C, sort them.
   (1, 0, 1)
   (2, 1, 0)
3. remove 2B from minimum heap, add 8D into minimum heap.
   (2, 1, 0)
   (6, 1, 1)
4. remove 3C from minimum heap, add 8D into minimum heap.
   (6, 1, 1)
   (5, 1, 1)
   sort them
   (5, 1, 1)
   (6, 1, 1)
   Remove 8D from minimum heap, which is bottom right, minimum effort is 5, not 6. The path is from 1A -> 3C -> 8D.

I do believe if I can read this short case study, then I can write the code in the contest or phone screen in 10 minutes. But I have to go over step by step to understand competition of two 8D entries in minimum heap in order to get minimum effort.

public class Solution {
        // (0,1),(1,0),(0,-1), (-1,0) four directions, simplified version
        private int[] directions = new int[] { 0, 1, 0, -1, 0 };
    
        /// Oct. 25, 2020
        /// study code: 
        public int MinimumEffortPath(int[][] heights)
        {
            int r = heights.Length;
            int c = heights[0].Length;
            bool[,] visited = new bool[r,c];
            
            // declare Tuple data type
            // https://docs.microsoft.com/en-us/dotnet/csharp/tour-of-csharp/types
            // new Tuple<int,int,int>( int H, int X, int Y) -> short hand -> (int H, int X, int Y)
            // default comparer ? 
            var sorted = new SortedSet<(int H, int X, int Y)>();
            
            sorted.Add((0, 0, 0)); 
            while (sorted.Count > 0)
            {
                // find smallest one in Height, if the same, then compare X, then compare Y
                // ask why? What is strategy? Find smallest one - greedy 
                // 
                var cur = sorted.Min;
                
                if (cur.X == r - 1 && cur.Y == c - 1)
                {
                    return cur.H;
                }
                
                visited[cur.X, cur.Y] = true;
                
                // Look up C# SortedSet source code - Remove API
                // very complicated - red black tree - find node and remove node
                // https://referencesource.microsoft.com/#system/compmod/system/collections/generic/sortedset.cs
                sorted.Remove(cur);
                
                for (int d = 0; d < 4; d++)
                {
                    int nx = cur.X + directions[d];
                    int ny = cur.Y + directions[d + 1];
                    
                    if(nx < 0 || nx == r || ny < 0 || ny == c || visited[nx,ny]) 
                    {
						continue;
                    }
                   
                    // all nodes in smallest path - smallest distance should be maximum one
                    var next = Math.Max(cur.H, Math.Abs(heights[cur.X][cur.Y] - heights[nx][ny]));
                    
                    sorted.Add((next,nx,ny));
                }
            }

            return 0;
        }
}

After mock interview

10/25/2020 3:58 PM 

I could not make it work in my mock interview as an interviewer, then I debugged the code using visual studio, and learned the detail the competition case in minimum heap. 

I recorded another video. 

Leetcode discuss: 414. Third Maximum Number

Here is the post.

C# SortedSet and minimum heap warm up practice in June 2020

June 2, 2020
It is an easy level algorithm. I like to review the code I wrote back in 2018 and then warmup C# SortedSet and how to implement a minimum heap using SortedSet.

Case study
The algorithm is to find third largest number in the array; if there are less than three distinct numbers, return maximum one.

How to approach the problem? Let me walk throught the test case and explain the approach.
Given an integer array, [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10].

Design a minimum heap using C# SortedSet, which is a set with unique values, but contains numbers sorted based on binary tree data structure. I will add some detail later.

The idea is to maintain a minimum heap with size three. If a new number is added to minimum heap, if the size is not less than 3, then the minimum one is removed from the heap. This is a little tricky, but it works perfect to translate "find third largest number" into "find minimum number in minimum heap in general".

Based on the integer array, [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10], the first three numbers are added to heap, [1, 2, 3], the fourth number is not in heap, so 4 is added to heap, minimum one with value 1 is removed; continue to work on second 4, skipped; continue to work on 5, 5 is added to heap, minimum one 2 is removed, [3, 4 , 5], until last one 10, heap is [8, 9, 10], return minimum one, value 8.

Here are highlights:

1. Design a minimum heap using C# SortedSet;
2. If there is less than three distinct numbers in the array, return maximum one;
3. Always keep minimum heap size on check, make sure that it is less and equal to 3;
4. More on step 3, if the size of heap is bigger than three, remove minimum one;
5. Go over all the numbers in the array, put them to heap;
6. Remove smallest one at the end.

My 2018 practice is here.

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

namespace Leetcode_414_third_maximum_number_SortedSet
{
    class Program
    {
        /// <summary>
        /// code review: June 2, 2020
        /// </summary>
        public class MinHeap
        {
            /// <summary>
            /// use SortedSet to implement the minimum heap 
            /// Also, duplicate integer is removed from SortedSet. 
            /// </summary>
            public SortedSet<int> sortedSet = new SortedSet<int>();

            public void Add(int val)
            {                
                sortedSet.Add(val);                
            }

            /// <summary>
            /// SortedSet<int> default is in ascending order. 
            /// 
            /// </summary>
            /// <returns></returns>
            public int PopMin()
            {
                int minKey = sortedSet.First();

                sortedSet.Remove(minKey);

                return minKey;
            }
        }

        static void Main(string[] args)
        {
            var result = ThirdMax(new int[] { 2, 2, 3, 1 });
            var result2 = ThirdMax(new int[] { 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10 });
            Debug.Assert(result2 == 8);
        }

        /// <summary>
        /// try to use MinHeap - August 15, 2018
        /// Requirement: 
        /// 1. Remove third maximum number;
        /// 2. If total of distinct numbers is less than three, remove maximum number. 
        /// Tips:
        /// 1. Design a minimum heap using C# SortedSet;
        /// 2. If there is less than three distinct numbers in the array, return maximum one;
        /// 3. Always keep minimum heap size on check, make sure that it is less and equal to 3;
        /// 4. More on step 3, if the size of heap is bigger than three, remove minimum one;
        /// 5. Go over all the numbers in the array, put them to heap;
        /// 6. Remove smallest one at the end. 
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int ThirdMax(int[] nums)
        {
            if (nums == null || nums.Length == 0)
                return -1;

            var length = nums.Length;
            var heap = new MinHeap();
           
            int index = 0;
            for (; index < length && heap.sortedSet.Count < 3; index++)
            {
                var current = nums[index];

                heap.Add(current);
            }

            // less than three distinct number in the array - return maximum one
            if (heap.sortedSet.Count < 3)
            {
                return heap.sortedSet.Last();
            }

            // heap.Set.Count = 3
            // Let us keep min heap size as 3 all the time
            // In other words, add one number to the heap, 
            // move the minimum one in the heap as well. 
            for (int i = index; i < length; i++)
            {
                var current = nums[i];
                if (heap.sortedSet.Contains(current))
                {
                    continue; 
                }

                heap.Add(current);
                heap.PopMin();                
            }

            return heap.PopMin();
        }
    }
}

Leetcode discuss: 215. Kth Largest Element in an Array

June 5, 2020

Here is the post.

C# SortedDictionary minimum heap practice II in June 2020

It is my second practice on this algorithm. I found out that my first practice has a unnecessary work to save -1 * element value in the array to minimujm heap. Here is the first practice. I think that my first practice shows weakness of my analytical skills using minimum heap; I should argue that minimum heap can deal with kth largest element algorithm perfectly, without using maximum heap.

Case study
Given an array, find kth largest element in the array. For example, array [1, 2, 3, 4, 5], k = 2, so kth largest element is value 4, index position = 3; We have to iterate all numbers in the array in order to find kth largest one.

If minimum heap is kept to size k, then kth largest one will be on top of minimum heap after last element is visited.

Kth largest element in the array can be solved using minimum heap, and heap size is also k. If k is not too largest, heap size is not an issue, then I just choose to go ahead to save element value in minimum heap; otherwise I can play the trick to save -1 * element value to reduce heap size.

Here are higlights:

1. Design a minimum heap and understand the importance to keep minimum heap size as k;
2. Use C# SortedDictionary<int, int> strong typing, value data type is count of same element value in the array;
3. Look into other C# data structure which may be best choice compared to SortedDictionary<int, int>

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

namespace _215_kth_largest_element
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// First practice: June 4, 2020
        /// </summary>
        public class MinHeap
        {
            /// <summary>
            /// use SortedDictionary to implement the minimum heap              
            /// </summary>
            public SortedDictionary<int, int> sorted = new SortedDictionary<int, int>();

            public void Add(int val)
            {
                if (sorted.ContainsKey(val))
                {
                    sorted[val]++;
                }
                else
                {
                    sorted.Add(val, 1);
                }
            }

            /// <summary>
            /// SortedDictionary<int> default is in ascending order. 
            /// 
            /// </summary>
            /// <returns></returns>
            public int PopMin()
            {
                int minKey = sorted.Keys.First();

                var count = sorted[minKey];
                if (count == 1)
                {
                    sorted.Remove(minKey);
                }
                else
                {
                    sorted[minKey]--;
                }

                return minKey;
            }
        }

        /// <summary>
        /// Find kth largest element in the array, not kth largest distinct element
        /// For example, [1, 2, 3, 4, 5], kth largest element is 4 if k = 2; how to find 4? 
        /// All elements should be searched, last one is 5, kth one should be minimum one on the top. 
        /// The tricky part is to keep minimum heap size as k
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int FindKthLargest(int[] nums, int k)
        {
            if (nums == null || nums.Length == 0 || k < 0)
                return -1;            

            var length = nums.Length;
            var heap = new MinHeap();

            // Let us keep min heap size as k all the time
            // In other words, add one number to the heap, 
            // move the minimum one in the heap as well if heap's size is bigger than k. 
            int size = 0;

            for (int i = 0; i < length; i++)
            {
                var value = nums[i];
                size++;

                heap.Add(value);

                if (size > k)
                {
                    heap.PopMin();
                }
            }

            return heap.PopMin();
        }
    }
}

treesminimum heapc# sorteddictionary

Leetcode discuss: 215. Kth Largest Element in an Array

Here is the post.

C# SortedDictionary minimum heap practice in 2020

June 4, 2020

Find kth largest element is very classical algorithm. I work on two tricky things to convert the problem into a minimum heap problem.

Warmup and best design talk

Let us walk through an example, how to design data structure heap for the help.
For example, integer array [1, 2, 3, 4, 5,6,7,8,9,10], k = 2
Minimum heap
Every number has to be went through, so the last one the heap should be [9, 10], the size is 2.
9 is the top of minimum heap.

Another example, still [1, 9, 2, 3, 4, 5, 6, 7, 8, 10], the last one the heap still should be [9, 10], the size is 2. Kth number is the top of heap.

The size of heap is important to find kth number in minimum heap. k = 2, heap size is 2.

If the array size is 10,000, number from 1 to 10,000, and then kth number is 9995, why we keep heap size as 9995, it is better to reverse the array in ascending order using -10,000 to -1. So the heap size can be 5 instead of 9995.

The exercise is warmup our design muscle and have a short break ice for real coding work.

Maximum heap
Since maximum heap can be processed using negative value of element array. We can stay with the minimum heap all the time.

Two tips
Work on a test case, array, [1, 2, 3, 4, 5], kth largest element, for example, 2th largest element is the fourth smallest element. Both are 4.

In order to apply kth largest element problem, it is to save -1 * element value. So largest one is converted into smallest one.If k is very big number close to size of array, then -1 * element will make sense, because n - k + 1 will be small integer, the minimum heap's size is small one.

Here are my highlights:

1. Design a minimum heap using SortedDictionary<int, int>, key is -1 * element value, value is count of element value; Notice that largest kth element not largest kth distinct element;
2. Write a class called MinHeap, two APIs, one is called Add(int val), second one is PopMin(), public property called sorted using SortedDictionary<int, int>;
3. Work on test case [1, 2, 3, 4,5], k = 2, 2th largest one is 4, and it is 4th smallest one. k -> n - k + 1 is the conversion mapping;
4. In order to get kth smallest minimum element, the heap size should be n - k + 1 at most.

Tips to share
I wrote a solution using minimum heap to find 814: third largest distinct element in the array, similar idea. The post is here.

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

namespace _215_kth_largest_element
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// First practice: June 4, 2020
        /// </summary>
        public class MinHeap
        {
            /// <summary>
            /// use SortedDictionary to implement the minimum heap              
            /// </summary>
            public SortedDictionary<int, int> sorted = new SortedDictionary<int, int>();

            public void Add(int val)
            {
                if (sorted.ContainsKey(val))
                {
                    sorted[val]++;
                }
                else
                {
                    sorted.Add(val, 1); 
                }
            }

            /// <summary>
            /// SortedDictionary<int> default is in ascending order. 
            /// 
            /// </summary>
            /// <returns></returns>
            public int PopMin()
            {
                int minKey = sorted.Keys.First();

                var count = sorted[minKey];
                if (count == 1)
                {
                    sorted.Remove(minKey);
                }
                else
                {
                    sorted[minKey]--;
                }

                return minKey;
            }
        }

        /// <summary>
        /// Find kth largest element in the array, not kth largest distinct element
        /// Save each element value * -1, so kth largest one will be (n - k + 1)th smallest one. 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int FindKthLargest(int[] nums, int k)
        {            
            if (nums == null || nums.Length == 0 || k < 0)
                return -1;

            k = nums.Length - k + 1; // convert largest kth to smallest 

            var length = nums.Length;
            var heap = new MinHeap();            
          
            // Let us keep min heap size as k all the time
            // In other words, add one number to the heap, 
            // move the minimum one in the heap as well if heap's size is bigger than k. 
            int size = 0; 
            
            for (int i = 0; i < length; i++)
            {
                var negativeValue = -1 * nums[i];
                size++; 

                heap.Add(negativeValue);

                if (size > k)
                {
                    heap.PopMin();
                }
            }

            return -1 * heap.PopMin();
        }
    }
}