Leetcode discuss: 1368. Minimum Cost to Make at Least One Valid Path in a Grid

 Here is the link. 

Nov. 25, 2020
Introduction
I paid Leetcode premium, and I struggled to learn to solve all those 14 set Google mock onsite interview algorithms. Just after I finished those algorithms, I found this algorithm. It is the best one compared to all those 14 set algorithms. I did come cross this hard level algorithm from an aritcle on Leetcode about Google phone screen written by an anonymous player.

I got stuck in first 15 minutes thinking, since I still have weak muscle in algorithm analysis, and I like to push myself using this hard level one. I solved 560 algorithms, I could code any solution and make it really readable and perfect in logic, efficient.

7 benefits to master the algorithm
I spent over 8 eight hours to read and share three practices. I am still not the master of the algorithm.

My first practice is here. I took BFS approach and work on a case study to help myself think better.

Second practice is here. I made minor changes to apply BFS algorithm, instead of using Queue, I chose to use C# LinkedList - Double linked list, a deque structure to enforce the cost with value 1 to be find first if possible. All nodes in the queue have cost difference less and equal to one.

Third practice is here. I tried the idea to implement the solution using dynamic programming.

Here are highlights:

1. Learn how to use BFS/ DFS, and also make minor modification from Queue to Deque;
2. Understand how to modify a medium level problem to find minimum path to a hard level one. This one is to add direction and cost to change direction, and make this subproblems are hard to define using dynamic programming.
3. This algorithm can help to solve a few other medium level algorithms, graph algorithms in general, minimum cost/ minimum distance/ greedy algorithm/ data structure.
4. Be humble. Since I was nervous when I thought about how to solve it by myself. I did not solve it before I came cross two day ago. I need to learn how to work on a simple case first.
5. I took distributed system and distributed algorithm, ad hoc network graduate course from 2002 to 2003 in Florida Atlantic University, but I did not write any code to help me understand the theorem. Now I practice a lot but I did not go back to learn and review more about theorems. Best way to learn is to practice a lot of algorithms first, and it will be easy to take any of those courses.
6. Play a simple test case very well in practice, and it will really help reduce stress in the interviews as an interviewee. Graph algorithm is tough but usually it can be solved using DFS/ BFS or union find algorithm.
7. As an interviewer, I can use the hard level algorithm to interview. Understand different stages of common mistakes, BFS/ DFS idea lacking, or other things.

I think that most important is to stay humble, continue to practice more hard level algorithm. Choose a hard level algorithm and really practice very well. Come back to review the algorithm very often as well.

Common mistakes - my mock interview as an interviewer
I can learn a lot to ask interviewees to solve the problem.
I asked the algorithm in mock interview as an interviewee, and the interviewee surprised me with bugs to write two while loop without thinking about BFS or DFS to cover all paths.

My first interviewee with buggy pseudo code.

def calculate_i_j(val):
    if val == 1:
        i = i
        j = j+1
    return i, j 
    

def modify_direction()
     return [possible_1 , possible_3]  # pair (i,j)

-- modification to find minimum cost 
calculate i, j from the current position's value
def find_Path()
    min_cost = 0 
    dp = 
    while i < len(rows) 
        while j < len(cols):
             cur_i, cur_j = calculate_i_j(grid[i][j])  // all directions -> 
             list_of_possible = modify_direction(i,j)
             for dir in list_of_possible:
                  i, j = dir
                  if i, j == cur_i, cur_j:
                      dp[i,j] = min(dp[i-1, j) , dp [i+1,j], dp[i,j+1], dp[i, j-1])
                  else:
                      dp[i,j] = 1+min(dp[i-1, j) , dp [i+1,j], dp[i,j+1], dp[i, j-1])
                  findPath(i,j)


-- old version has a bug
calculate i, j from the current position's value
def find_Path()
    min_cost = 0 
    while i < len(rows) 
        while j < len(cols):
             i, j = calculate_i_j(grid[i][j])
             if i >len(rows) or j > len(cols) or i< 0 or j <0: # crossing the boundaries

                  list_of_possible = modify_direction()
                  for dir in list_of_possible:
                       cost = 1+ find_Path(dir[0], dir[1])
                       min_cost = min(cost, min_cost)                     
    recursively_move(i, j)
end

Interviewee asked feedback and hints

1. Missing dp[row, col], save every position minimum cost
2. Exhaust all paths, use data structure, BFS, use Queue for example.

Improve analysis:
Work on a simple matrix 2 x 2.

all possible (0,0) -> (1, 1)
<- <- maximum cost -> rows + columns -> 0 -> binary search
-> ->

all paths -> miss a path -> all paths
snake - rows * columns - length ->cost 0 ->
paths -
complexity -
reduce
BFS / DFS - queue

(0,0) -> possible analysis - space, complexity

dp[i, j]  - minimum cost from (0,0) to (i, j)
exhaust all paths - (3, 3) - keep minimum cost - path - minimum 3 -> 5 <- 
current minimum cost -> 3    

<-  -> ->  ->1    
<-1 -> 2<-1 <-  <- 
->  -> ->  -> 
<-  <- <-  <- 

Go over (1, 1) position, from left, cost is 1, and from right cost is 2
<-  -> ->  ->1    
<-1 -> 2<-1 <-  <- 
->  -> ->  -> 
<-  <- <-  <- 

BFS - breadth first search 

Leetcode discuss: 1368. Minimum Cost to Make at Least One Valid Path in a Grid

 Here is the link. 

First practice - C# - BFS - Case study

Nov. 23, 2020
Introduction
From the comment on the article about Google onsite interview, I decided to work on this hard level algorithm. I tried to think about how to solve it by myself, but I could not come out the details using BFS to solve it. I need to work on a small example, step by step, try to solve it by hand first.

Case study
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
How to solve the problem ?
Record minimum cost for each position in the matrix.

cost[0][0] = 0,
Apply BFS algorithm, start from (0,0), go right to (0, 1) or go down to (1, 0).
grid[0][0] = 1 which is to go right, so cost[0][1] = 0, no need to change the direction.
But cost[1][0] = 1 since direction should go down.
so the cost matrix
0, 0, ?, ?
1, ?, ? , ?
?, ?, ?, ?
?, ?, ?, ?
Next step is to put position (0, 1) and (1, 0) to the queue, and continue to apply BFS algorithm.
Check (0, 1), there are three directions, go left or right or down. Go right, no cost. Go left, cost 1, but cost(0,0) = 0, new path is bigger than 0. Ignore.
Cost matrix is the following:
0, 0, 0, ?
1, 1, ?, ?
?, ?, ?, ?
Skip rest of steps.

What if the above step to put neighbor nodes of (0,0) down first, right next, (1,0) and (0, 1).
(1, 0) has two directions to go, either go right or go down, so the cost of matrix is updated.
0, 0, ?, ?
1, 2, ?, ?
1, ?, ?, ?
?, ?, ?, ?
(0, 1) has two directions to go, eith go right or go down, so the cost of matrix (1, 1) is 1 < 2, so the minimum cost 1 should replace 2, which is the path from (0, 0) to go down and then go right.

I think that it is important to go over a simple test case step by step, so next time I can figure out how to solve the problem in onsite interview, like Google onsite.

Here are lessons I learn from this practice:

1. BFS algorithm - the order of neighbor nodes into the queue should not matter in final result. Shortest cost path may not be found first, so it is important to update cost when a new path is found with minimum cost.
2. It is a graph algorithm. The longer path may have smaller cost.

BFS solution
Declare cost[rows][] array to save minimum cost from (0,0) to (row, col). Apply BFS algorithm, and each step four directions are considered, and then cost will be calculated if the direction is different from the one given in grid[][].

The challenge idea is to find minimum cost to each node (row, col).

Deep thoughts
Nov. 24, 2020 10;35 PM

I asked the interviewee in my mock interview, and then I thought about more carefully. BFS algorithm will exhaust all possible paths, so that minimum cost will be calculated to reach (rows -1 , columns - 1).

If there are two loops, it should not work. The interviewee wrote the solution and I do believe that it will not exhaust all possible paths and each position will have minimum path from start position (0, 0).

The interviewee wrote the code like this:
while i < len(rows)
while j < len(cols)
i, j = calculate_i_j(grid[i][j])
if i > len ...

public class Solution {
    public int MinCost(int[][] grid)
    {            
        var rows = grid.Length; 
        var columns = grid[0].Length; 
        
	    var cost = new int[rows][];
        for(int row = 0; row < rows; row++)
        {
            cost[row] = new int[columns];
        }

	    for (int row = 0; row < rows; row++)
	    {
		    for (int col = 0; col < columns; col++)
		    {
			    cost[row][col] = int.MaxValue;
		    }
	    }
                
	    cost[0][0] = 0;

	    var queue = new Queue<int[]>();
	    queue.Enqueue(new int[]{0, 0});

        //                              right,    left,      down,      up 
        var directions = new int[,] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        //  1 -> right, 2 <- left, 3 down, 4 up 
        
	    while (queue.Count > 0)
	    {
		    var node = queue.Dequeue();
            var row = node[0];
            var col = node[1];
            
		    int currentCost = cost[row][col];

		    for (int i = 0; i < directions.GetLength(0); i++)
		    {
			    var nextRow = row + directions[i, 0];
			    var nextCol = col + directions[i, 1];
                
                // grid[x][y] has 4 values 
                //  1 -> right, 2 <- left, 3 down, 4 up 
			    int newCost = currentCost + (grid[row][col] == (i + 1) ? 0 : 1); 

			    if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < columns)
			    {
                    // current path is shorter one
				    if (newCost < cost[nextRow][nextCol])
				    {
					    cost[nextRow][nextCol] = newCost;
					    queue.Enqueue(new int[]{nextRow, nextCol});
				    }
			    }
		    }
	    }

	    return cost[rows - 1][columns - 1];
    }
}

Leetcode discuss: 1368. Minimum Cost to Make at Least One Valid Path in a Grid

 Here is the link. 

Second practice - C# - no cost direction first - case study

Nov. 24, 2020
It is more efficient to handle no cost direction first using BFS, so I like to practice using C# LinkedList instead of Queue to handle the neighbor nodes.

Case study
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
How to solve the problem ?
Record minimum cost for each position in the matrix.
Using C# double linked list LinkedList, a deque data structure.

cost[0][0] = 0,
Apply BFS algorithm, start from (0,0), go right to (0, 1) or go down to (1, 0).
grid[0][0] = 1 which is to go right, so cost[0][1] = 0, no need to change the direction.
But cost[1][0] = 1 since direction should go down.
So add (0, 1) to the head of linked list, and add (1, 0) to the end of double linked list.

so the cost matrix
0, 0, ?, ?
1, ?, ?, ?
?, ?, ?, ?
?, ?, ?, ?

Next step is to visit linked list and continue to apply BFS algorithm. Work on the head of linked list first, which is (0, 1).

Check (0, 1), there are three directions, go left or right or down. Go right, no cost. Go left, cost 1, but cost(0,0) = 0, new path is bigger than 0. Ignore.
Cost matrix is the following:
0, 0, 0, ?
1, 1, ?, ?
?, ?, ?, ?

So cost matrix will be the following:
0, 0, 0, 0
1, 1, 1, 1
?, ?, ?, ?,
?, ?, ?, ?

The linked list has four nodes in the order of {[1, 0],[1, 1],[1, 2],[1, 3]}.

I think that the above steps are good enough to figure out how to find minimum cost from top left to bottom right. The next step is to work on coding. One thing is to talk about time complexity.

Double linked list
Instead of using Queue, I choose to use C# LinkedList, all neighbor nodes with no cost will be added to front of linked list, nodes with cost will be added to the end of linked list.
C# LinkedList.AddFirst for no cost direction
C# LinkedList.AddLast for cost direction

To remove a node from the linked list, remove from the head of linked list. To understand design of C# LinkedList, a C# LinkedListNode is returned from LinkedList.RemoveFirst API call.

It is important for me to remember all those LinkedListNode APIs:
Properties
List
Next
Previous
Value
ValueRef

Questions to ask
Common mistakes and questions asked:

1. What is most important in this problem solving? All possible paths should be examined so that minimum cost will be calculated correctly from top left corner to bottom right.
2. How to ensure that all paths will be examined? What to keep in the search?
3. Why do min cost of each position (row, col) in matrix should be calculated in order to get the bottom-right one?
4. Why does the solution using two loops, one is to iterate each row, one is to iterate each column, it is not working? Is it a common mistake from interviewees?

public class Solution {
     /// <summary>
        /// Nov. 24, 2020
        /// BFS approach 
        /// Work on BFS approach - work on no cost direction first, and then directions with cost next
        /// Using C# LinkedList instead of Queue, deque - two ends. 
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public int MinCost(int[][] grid)
        {
            var rows = grid.Length;
            var columns = grid[0].Length;

            var cost = new int[rows][];
            for (int row = 0; row < rows; row++)
            {
                cost[row] = new int[columns];
            }

            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < columns; col++)
                {
                    cost[row][col] = int.MaxValue;
                }
            }

            cost[0][0] = 0;

            var list = new LinkedList<int[]>();
            list.AddLast(new int[] { 0, 0 });

            //                              right,    left,      down,      up 
            var directions = new int[,] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
            //  1 -> right, 2 <- left, 3 down, 4 up 

            while (list.Count > 0)
            {
                var node = list.First;
                list.RemoveFirst();

                // C# LinkedListNode - Value - get, set, Next, Previous
                // https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlistnode-1.value?view=net-5.0
                var row = node.Value[0];
                var col = node.Value[1];

                int currentCost = cost[row][col];

                for (int i = 0; i < directions.GetLength(0); i++)
                {
                    var nextRow = row + directions[i, 0];
                    var nextCol = col + directions[i, 1];

                    // grid[x][y] has 4 values 
                    // 1 -> right, 2 <- left, 3 down, 4 up 
                    var noAdditionalCost = grid[row][col] == (i + 1);
                    int newCost = currentCost + (noAdditionalCost ? 0 : 1);

                    if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < columns)
                    {
                        // current path is shorter one
                        if (newCost < cost[nextRow][nextCol])
                        {
                            cost[nextRow][nextCol] = newCost;
                            var nextPosition = new int[] { nextRow, nextCol };

                            if (noAdditionalCost)
                            {
                                list.AddFirst(nextPosition);
                            }
                            else
                            {
                                list.AddLast(nextPosition); 
                            }
                        }
                    }
                }
            }

            return cost[rows - 1][columns - 1];
        }
}

Equity research: I am back and I like to work hard

 Go over finviz.com and start to learn more about business. 

 Today I went over a few stocks, and I am looking for good stocks to invest in short term or long term. 

 I like to be open and be a hard working good researcher. 

NYSE EXPR: 300% gains from Nov. 6, 0.62 - Nov. 24, 1.54

 Nov. 24, 2020

Introduction

It is important for me to stay in current. Look for best opportunity in stock market. Take some risk. 

Let SU.TO stock and Canadian oil stocks be the history. Embrace new challenge with those distress retail clothing store. 

I like to be an investor and then try to stay in long term as well. 

EXPR - Express, Inc. 

My favorite brand and I wish that small business can survive. 

Thanks Anna to be a good researcher. She is such hard working lady and gets up early at 5:00 AM every day. 

Equity research is most important for us. There is a fair opportunity for all of us to build wealth in this coronavirus special time, once a century opportunity. 

Lalit Kundu: #CodingInterviewWeekly series: Exploring a dynamic programming and graphs Google interview

 Here is the link. 

You are in a matrix where each cell has some coins placed on it. You can move in either of the 4 directions (up, left, right, bottom) where the movement is possible only if the cell you want to move to has strictly greater number of coins than your current cell. You can start from any cell. What is the maximum length of the path you can move? 

Let's also try a follow-up: Find a cell from which maximum number of cells are reachable using the rules we've mentioned. 

Leetcode 329. Longest Increasing Path in a Matrix, hard level algorithm. My last practice is on May 23, 2019.

Jianmin Chen6 days ago (edited)

I am preparing google onsite on Dec. 8, 2020. I watched the video again and agin, and after I spent time to go over Leetcode 329 Longest increasing path in a matrix (hard level), my last practice in 2019 and all other sharings, I started to understand your teaching much better. You covers so many topics: dp states, infinity loop, DAG, recursive function, best algorithm lesson in the world. I am really curious and like to learn more about hire and strong hire in last five minutes.

1

REPLY

Hide reply

Probing with Lalit Kundu

5 days ago

Glad you find it useful - you're right, I have a habit of digressing into literally everything that's related to the crux of the problem :) In future videos, I will surely talk about various aspects of the interviews - such as interviewer ratings, implementation tips etc. - stuff that I haven't covered in this video.