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