Count shortest distance in grid

Question

Given a 2D grid of non-negative integers representing the cost of moving through each cell, write a function to calculate the shortest distance from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any point in time. The function should return the minimum cost to reach the bottom-right corner.

Codemia · Accepted Answer

The problem can be analyzed as a pathfinding problem on a grid where each cell has a cost associated with moving through it. The goal is to find the shortest path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1), where m and n are the dimensions of the grid. Since we can only move down or right, this is a dynamic programming problem where we can build up solutions for smaller subproblems to find the solution for the overall problem.

We will utilize dynamic programming to solve this problem. The idea is to create a 2D DP array where `dp[i][j]` represents the minimum cost to reach the cell (i, j). The algorithm proceeds as follows:

1. Initialize a DP table of the same size as the grid. Set `dp[0][0]` to `grid[0][0]` since that's the starting point.
2. Fill the first row by accumulating costs from left to right because the only way to reach any cell in the first row is from its left neighbor.
3. Fill the first column similarly, accumulating costs from top to bottom.
4. For each cell `(i, j)`, compute the minimum cost to reach that cell by taking the minimum of the costs from the top cell `(i-1, j)` and the left cell `(i, j-1)`, and add the cost of the current cell: `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`.
5. The value in `dp[m-1][n-1]` will give us the minimum cost to reach the bottom-right corner.

Here is the Python implementation of the above approach:

```python
def min_cost_path(grid):
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]

for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

return dp[m-1][n-1]
```

The time complexity of this solution is O(m * n) because we iterate through each cell in the grid exactly once to fill the DP table. The space complexity is also O(m * n) due to the storage required for the DP table. If we want to optimize space, we could use a single-dimensional array to store only the current and previous rows, reducing the space complexity to O(n).

1. **Empty Grid**: If the grid is empty, we should return 0 because there's no path to calculate.
2. **Single Cell Grid**: If the grid consists of only one cell, the cost is simply the value of that cell.
3. **Grid with One Row or One Column**: If the grid has only one row or one column, the minimum cost will be the sum of the values along that row or column.
4. **Large Values**: Consider scenarios where grid values are large (e.g., maximum integer limits) to ensure that the sum does not cause overflow (in Python, this is not an issue due to dynamic integers).

Count shortest distance in grid

Airbnb

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Airbnb Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string