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:
- Start from top left node in the matrix, define C# Tuple<int, int,int>(int Height, int row, int col);
- 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.
- 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.
- Make sure that visit all nodes in the order based on minimum distance until bottom right node is reached.
- 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:
- 1A, (0, 0, 0)
- remove 1A from heap, add 2B and 3C, sort them.
(1, 0, 1)
(2, 1, 0) - remove 2B from minimum heap, add 8D into minimum heap.
(2, 1, 0)
(6, 1, 1) - 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 {
private int[] directions = new int[] { 0, 1, 0, -1, 0 };
public int MinimumEffortPath(int[][] heights)
{
int r = heights.Length;
int c = heights[0].Length;
bool[,] visited = new bool[r,c];
var sorted = new SortedSet<(int H, int X, int Y)>();
sorted.Add((0, 0, 0));
while (sorted.Count > 0)
{
var cur = sorted.Min;
if (cur.X == r - 1 && cur.Y == c - 1)
{
return cur.H;
}
visited[cur.X, cur.Y] = true;
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;
}
var next = Math.Max(cur.H, Math.Abs(heights[cur.X][cur.Y] - heights[nx][ny]));
sorted.Add((next,nx,ny));
}
}
return 0;
}
}
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.
