Custom state while iterating over a recursive data structure
— Tricks — 2 min read
When iterating over a graph over a recursive data structure, we can utilize a custom iteration state. What I mean by this is storing additional helpful information for the given iteration. This would usually be a distance from the current node or similar variables.
Example: Shortest Path in Binary Matrix
Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
All the visited cells of the path are 0. All the adjacent cells of the path are 8-directionally connected (i.e., they are different, and they share an edge or a corner). The length of a clear path is the number of visited cells of this path.
In this example, we can notice that we can use BFS to traverse the grid.
Our first thought could be to use level order traversal to solve this, but this would be incorrect.
Custom state comes very handy in this case. Let's think what we can store... we need to keep track of the distance right?
Instead, on each iteration we would store a custom state of (row, col, distance) for each coordinate.
This would then give us our shortest path if we reach the coordinates of
row == n-1 and col == n-1
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:N = len(grid)if grid or grid[N-1][N-1]:return -1# custom state: row, col, distanceq = deque([(0,0,1)])seen = set()seen.add((0,0))# move in 4 directions + diagonallydirs = [[0,1], [1,0], [0,-1], [-1,0], [1,1], [-1,1], [1,-1], [-1,-1]]while q:r, c, dist = q.popleft()if r == c == N-1:return distfor dx, dy in dirs:nr, nc = r + dx, c + dyif (0 <= nr < N and 0 <= nc < N and(nr, nc) not in seen andgrid[nr][nc] == 0):q.append((nr, nc, dist+1))seen.add((nr, nc))return -1