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];
    }
}