Problem Statement in English
You’re given an $n \times n$ matrix grid. Your task is to find the number of steps in the shortest path from the co-ordinate $(0,0)$, to $(n - 1, n - 1)$. You can only step on elements that have a value of $0$.
You are also allowed to travel from a node to any of its $8$ neighbours.
Approach
We can only begin looking for a path if the index $(0,0)$ has a value of $0$. If it is, we add it to the queue.
From here, we can check the $8$ neighbours of the node to check if they’re valid nodes that we can step on. If they are, we add them to the queue. We need to keep track of the nodes that we visit, so that we avoid redundant computations. Hence, as and when we visit a new node, we add it to a Set that we check before processing a node in the future.
But how do we find the shortest path to the destination node? In order to do that we need to keep track of the number of steps taken to get to a specific node. We can do so by keeping track incrementally.
For example, to get to $(0,0)$, we’ve needed $1$ step. So we push $(0,0)$ into the queue along with the number $1$ indicating that we took $1$ step to get to that node. When we go a co-ordinate from there, say $(x,y)$, we will push the co-ordinate to the queue along a value of $1+1$, indicating that it took us $2$ steps to get here.
But why a Breadth First Search? Why not a Depth First Search?
Because in a Breadth First Search, we’re guaranteed to find the shortest path to an immediate neighbour before we find a longer path. Here’s a quick graph illustration:
Let’s quickly name the nodes:
- Top Left: $L$
- Top Right: $R$
- Bottom: $B$
Imagine you start at node $L$. It’s guaranteed to find node $B$ before $R$ finds the path to it. Let’s trace the BFS Queue really quick:
- q = [$L$]
- q = [$R$, $B$]
Notice how we’ve already reached $B$ at this point. In the next step we would have processed $R$, and rediscovered $B$. But then, when we check our Set, we’ll realize that we’ve already visited the node, and hence we skip it.
This is how we guarantee finding the shortest path, and discarding other options, hence reducing the amount of computation needed for the task.
Solution in Python
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] == 0 and len(grid) == 1 and len(grid[0]) == 1:
return 1
if grid[0][0] != 0:
return -1
q = deque()
seen = set()
# since in the worst case we can have a 10 x 10 matrix
# and because I didn't want to calculate the length of this matrix,
# it's kind of unnecessary
shortestPath = 10000
# we have to start from this node
q.append([(0, 0), 0])
while len(q) != 0:
val = q.popleft()
row = val[0][0]
col = val[0][1]
distTravelled = val[1] + 1
# we've reached the destination, see if it's the shortest
if val[0] == (len(grid) - 1, len(grid[0]) - 1):
shortestPath = min(shortestPath, distTravelled)
continue
# same row, next col
if (
col + 1 < len(grid[row])
and grid[row][col + 1] == 0
and f"{row} {col+1}" not in seen
):
q.append([(row, col + 1), distTravelled])
seen.add(f"{row} {col+1}")
# same row, prev col
if (
col - 1 >= 0
and grid[row][col - 1] == 0
and f"{row} {col-1}" not in seen
):
q.append([(row, col - 1), distTravelled])
seen.add(f"{row} {col-1}")
# prev row, same col
if (
row - 1 >= 0
and grid[row - 1][col] == 0
and f"{row-1} {col}" not in seen
):
q.append([(row - 1, col), distTravelled])
seen.add(f"{row-1} {col}")
# next row, same col
if (
row + 1 < len(grid)
and grid[row + 1][col] == 0
and f"{row+1} {col}" not in seen
):
q.append([(row + 1, col), distTravelled])
seen.add(f"{row+1} {col}")
# prev row, prev col
if (
row - 1 >= 0
and col - 1 >= 0
and grid[row - 1][col - 1] == 0
and f"{row-1} {col-1}" not in seen
):
q.append([(row - 1, col - 1), distTravelled])
seen.add(f"{row-1} {col-1}")
# prev row, next col
if (
row - 1 >= 0
and col + 1 < len(grid[row])
and grid[row - 1][col + 1] == 0
and f"{row-1} {col+1}" not in seen
):
q.append([(row - 1, col + 1), distTravelled])
seen.add(f"{row-1} {col+1}")
# next row, prev col
if (
row + 1 < len(grid)
and col - 1 >= 0
and grid[row + 1][col - 1] == 0
and f"{row+1} {col-1}" not in seen
):
q.append([(row + 1, col - 1), distTravelled])
seen.add(f"{row+1} {col-1}")
# next row, next col
if (
row + 1 < len(grid)
and col + 1 < len(grid[0])
and grid[row + 1][col + 1] == 0
and f"{row+1} {col+1}" not in seen
):
q.append([(row + 1, col + 1), distTravelled])
seen.add(f"{row+1} {col+1}")
pass
return shortestPath if shortestPath != 10000 else -1
Note: I’ve gone with a very verbose neighbour hard coding, because I find it more readable, albiet slightly lengthier. You could instead store relative weights to neighbours and dynamically calculate the $8$ neighbours of a node using a nested loop.
Complexity
Time: $O(n^2)$
Since in the worst case we visit all the elements in the $n \times n$ matrix, and $n*n=n^2$.Space: $O(n^2)$
Since in the worst case we store all the elements in the $n \times n$ matrix in theSet, and $n*n=n^2$.
Mistakes I Made
I didn’t account for edge cases like grid = [[0]], and `grid = [[1]].
And we are done.