Problem Statement in English

You’re given two integers row and col representing the dimensions of a grid, and an array cells where $cells[i] = [r_i, c_i]$ indicates that on the i-th day, the cell at position $(r_i, c_i)$ becomes flooded (1-indexed).

Approach

We basically have to try the state for each day and determine if we can cross from the top row to the bottom row.

But we can reduce the number of days we have to try using binary search. This is because the state from day d is always carried over to day d + 1, albeit with one more flooded cell.

So if we can cross on day d, we can definitely cross on any day before d. Similarly, if we cannot cross on day d, we cannot cross on any day after d.

To determine if we can cross on a given day, we can use either depth first search (DFS) or breadth first search (BFS). Basically just try to traverse from any cell in the top row to any cell in the bottom row, avoiding flooded cells.

Solution in Python


class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        def good(day):
            matrix = [[0 for _ in range(col)] for _ in range(row)]
            for i, j in cells[: day + 1]:
                matrix[i - 1][j - 1] = 1

            q = deque()
            seen = set()
            for i in range(col):
                if matrix[0][i] != 1:
                    q.append((0, i))

            while q:
                x, y = q.pop()

                if (x, y) in seen:
                    continue
                seen.add((x, y))

                for dx, dy in directions:
                    nx, ny = x + dx, y + dy

                    if (
                        (nx, ny) not in seen
                        and 0 <= nx < row
                        and 0 <= ny < col
                        and matrix[nx][ny] == 0
                    ):
                        if nx == row - 1:
                            return True
                        q.append((nx, ny))

            return False

        l, r = 0, len(cells) - 1
        res = l
        while l <= r:
            mid = (l + r) // 2

            if good(mid):
                res = mid
                l = mid + 1
            else:
                r = mid - 1

        return res + 1

Complexity

  • Time: $O(row \times col \times \log(cells))$
    Since we are performing a binary search over the number of days (length of cells), and for each day we are performing a BFS/DFS which takes $O(row \times col)$ time, the overall time complexity is $O(row \times col \times \log(cells))$.

  • Space: $O(row \times col)$
    Since we make a matrix of size row x col and a queue for BFS/DFS, the space complexity is $O(row \times col)$.

Mistakes I Made

I made my binary search update mid = r - 1. 🤦‍♂️

And we are done.