< Back 1970. Last Day Where You Can Still Cross I LOVE graph questions. We're given a matrix of 0s and a list of cells defined by time, t, where each index defines the time where cell[t] will fill up with water. We're asked to determine the last day we can cross from the top of the matrix to the bottom. We can only traverse cells if they're not filled with water. Per usual, we can travel in the four cardinal directions. We solve this with binary search and breadth first search. Our lower and upper bounds will be time 0 and len(cells) - 1, the final day to cross. During each step of the binary search, we acquire a set of flooded cells up to the current day, t. We then conduct a breadth first search from the start cells, less the flooded ones, to see if we can reach and end cell. If we can, we terminate and return True. If not, we return False. If we can reach the end, we know that we're not waiting long enough. If we can't we know that we've waiting too long. For these situations respectively, we set l = m, searching in the right side of the search space, or we set r = m - 1, searching in the left side of the search space. Eventually, l will be equal to r, and we'll return l, the last day we can cross. The solution is as follows: class Solution: def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int: directions = [(0, -1), (0, 1), (-1, 0), (1, 0)] starts = set((0, j) for j in range(col)) ends = set((row - 1, j) for j in range(col)) l, r = 0, len(cells) - 1 def is_valid(y: int, x: int) -> bool: return -1 < y < row and -1 < x < col def bfs(flooded: set) -> bool: seen = set() for y, x in starts: if (y + 1, x + 1) not in flooded: seen.add((y, x)) queue = list(seen) while queue: curr_queue, queue = queue, [] for y, x in curr_queue: for dy, dx in directions: ny, nx = y + dy, x + dx if is_valid(ny, nx) and (ny, nx) not in seen and (ny + 1, nx + 1) not in flooded: if (ny, nx) in ends: return True queue.append((ny, nx)) seen.add((ny, nx)) return False while l < r: m = r - (r - l) // 2 flooded = set(tuple(cell) for cell in cells[:m]) if bfs(flooded): l = m else: r = m - 1 return l _ Time Complexity: O(m * n log(k)) - Where m and n are the row and col dimensions of the matrix. We perform binary search k times, the number of cells in the cells list. BFS takes O(m * n) time. _ Space Complexity: O(m * n) - During BFS, we have at most m * n cells in the queue.