< 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.