Google Interview Question — LeetCode 1368

In this post, we are going to discuss leetcode 1368 — Minimum Cost to Make at Least One Valid Path in a Grid, which is recently asked in Google interviews.

Problem Analysis

Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some signs on the cells of the grid that point outside the grid.

You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]] 
Output: 3 
Explanation: You will start at point (0, 0). The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3) The total cost = 3.

This is a graph problem with the Dijkstra Algorithm.

My Thinking Process

For graph problems to find the minimum cost from one state to another state, we usually use the Dijkstra Algorithm.

The Dijkstra Algorithm is the same as BFS structure, but with the following differences:

1. Use a heapq instead of the regular queue. The items in the queue would be the state, with their costs.
2. Define the state. In this case, the state would simply be the position in the grid. We just need to find the minimum cost to each state.
3. Maintain a cost map, which keeps track of the cost for each state.
4. Initialize the cost to all the state to be infinite.

Code Implementation

Base on the analysis above, below is my implementation of the problem.