0698HardArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMatrix

Last Day the Flats Stay Walkable

Tracked in this browser only

Trains the technique from

LeetCode 1970Last Day Where You Can Still Cross

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tidal flat is laid out as a grid of rows rows and cols columns. Rows are numbered 1 through rows starting at the north jetty, so row 1 runs along the north jetty and row rows runs along the south jetty. Columns are numbered 1 through cols from west to east.

Every square starts dry. Days are numbered from 1, and on day d the square floods[d - 1] = [r, c] goes under water and stays under from then on. The list covers every square of the flat exactly once, so by day rows * cols nothing is dry.

A walk across on a given day starts on any dry square in row 1, ends on any dry square in row rows, and moves from a square to a dry square sharing a side with it, meaning one step north, south, east or west. Diagonal steps are not allowed, and every square on the walk must be dry that day.

Return the largest day number on which a walk across is still possible.

Examples

Example 1

Input: rows = 3, cols = 3, floods = [[2, 2], [1, 1], [3, 3], [1, 3], [3, 1], [2, 1], [2, 3], [1, 2], [3, 2]]
Output: 2

On day 2 the flooded squares are (2,2) and (1,1). The route (1,3), (2,3), (3,3) starts in row 1 on the north jetty, steps south twice onto dry squares, and finishes in row 3 on the south jetty. On day 3 the square (3,3) also floods.

Example 2

Input: rows = 2, cols = 3, floods = [[1, 2], [2, 2], [1, 1], [2, 3], [1, 3], [2, 1]]
Output: 3

After the first three squares flood, the dry squares are (1,3), (2,1) and (2,3), and the step from (1,3) to (2,3) crosses from the north jetty row to the south jetty row.

Example 3

Input: rows = 4, cols = 4, floods = [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3], [4, 1], [4, 2], [4, 3], [1, 4], [2, 4], [3, 4], [4, 4]]
Output: 12

The first twelve days flood columns 1, 2 and 3 completely and leave column 4 untouched, so on day 12 the four squares of column 4 form a walk from the north jetty row to the south jetty row. Column 4 starts flooding on day 13.

Constraints

2 <= rows, cols <= 2 * 10^4
4 <= rows * cols <= 2 * 10^4
floods.length == rows * cols
floods[i].length == 2
1 <= floods[i][j] <= 2 * 10^4
Each floods[i] is [r, c] with 1 <= r <= rows and 1 <= c <= cols, and no square is listed twice.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def last_dry_day(rows: int, cols: int, floods: list[list[int]]) -> int:

Java

public int lastDryDay(int rows, int cols, int[][] floods)

The intended approach

Time O(rows * cols * log(rows * cols)): one linear fill per candidate day.Space O(rows * cols) for the wet and visited grids and the queue.

Flooding is one-way, so once a day has no walk across, no later day has one either, and the days split into an early stretch that works and a late stretch that does not. Search for that split point, and for a candidate day mark the squares flooded up to it, then run a breadth-first flood fill seeded with every dry square of row 1 and report whether it reaches row `rows`. The fill is driven from a queue, so the flat's size never stresses the call stack.

Pythonentry point: last_dry_day

from collections import deque


def last_dry_day(rows, cols, floods):
    total = rows * cols

    def crossable(day):
        wet = [[False] * cols for _ in range(rows)]
        for d in range(day):
            r, c = floods[d]
            wet[r - 1][c - 1] = True
        seen = [[False] * cols for _ in range(rows)]
        queue = deque()
        for c in range(cols):
            if not wet[0][c]:
                seen[0][c] = True
                queue.append((0, c))
        while queue:
            r, c = queue.popleft()
            if r == rows - 1:
                return True
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and not wet[nr][nc] and not seen[nr][nc]:
                    seen[nr][nc] = True
                    queue.append((nr, nc))
        return False

    # a day that allows a crossing is preceded only by days that also allow one,
    # because flooding never uncovers a square, so the days split at one point
    lo = 1
    hi = total - 1
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if crossable(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

The obvious version

Run time backwards with a disjoint-set structure. Start from a fully flooded flat and turn squares dry in reverse day order, joining each newly dry square to its dry side neighbours and, when it lies on a jetty row, to a sentinel node for that jetty. The first day at which the two jetty sentinels land in the same set is the answer, and no search over candidate days is needed.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_last_dry_day(rows, cols, floods):
    total = rows * cols
    parent = list(range(total + 2))
    NORTH = total
    SOUTH = total + 1

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def join(a, b):
        ra = find(a)
        rb = find(b)
        if ra != rb:
            parent[ra] = rb

    dry = [False] * total
    # walk the days backwards: on day d the dry squares are exactly the ones
    # that flood on day d and later, so each step back turns one more square dry
    for d in range(total - 1, 0, -1):
        r, c = floods[d]
        idx = (r - 1) * cols + (c - 1)
        dry[idx] = True
        if r == 1:
            join(idx, NORTH)
        if r == rows:
            join(idx, SOUTH)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r + dr
            nc = c + dc
            if 1 <= nr <= rows and 1 <= nc <= cols:
                nidx = (nr - 1) * cols + (nc - 1)
                if dry[nidx]:
                    join(idx, nidx)
        if find(NORTH) == find(SOUTH):
            return d
    return 0

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in