Last Day Where You Can Still Cross

Hard
1736.

Last Day Where You Can Still Cross

Last Day Where You Can Still Cross is a hard coding problem on arrays, depth-first search and binary search, asked in Amazon and Google interviews.

A row x col matrix of land floods one cell per day. On day 0 every cell is land. On day i (1-based) the cell cells[i - 1] = [ri, ci] becomes water — coordinates are 1-based, so [1, 1] is the top-left cell.

You want to walk from any cell of the top row to any cell of the bottom row, stepping only on land and moving up, down, left or right.

Return the last day on which such a walk is still possible.

Example 1

Input
row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
Output
2
Explanation
After day 2 the right column is still land; on day 3 the top-right cell floods and the top row is all water.

Example 2

Input
row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
Output
1

Example 3

Input
row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
Output
3

Constraints

  • 2 <= row, col <= 2 * 10^4
  • 4 <= row * col <= 2 * 10^4
  • cells.length == row * col
  • 1 <= ri <= row
  • 1 <= ci <= col
  • all the values of cells are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} row
 * @param {number} col
 * @param {number[][]} cells
 * @return {number}
 */
var latestDayToCross = function(row, col, cells) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Last Day Where You Can Still Cross — Problem & Solution

Last Day Where You Can Still Cross solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Last Day Where You Can Still Cross is a hard coding problem on arrays, depth-first search and binary search, asked in Amazon and Google interviews.

Problem statement

A row x col matrix of land floods one cell per day. On day 0 every cell is land. On day i (1-based) the cell cells[i - 1] = [ri, ci] becomes water — coordinates are 1-based, so [1, 1] is the top-left cell.

You want to walk from any cell of the top row to any cell of the bottom row, stepping only on land and moving up, down, left or right.

Return the last day on which such a walk is still possible.

Example 1

Input: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
Output: 2
Explanation: After day 2 the right column is still land; on day 3 the top-right cell floods and the top row is all water.

Example 2

Input: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
Output: 1

Example 3

Input: row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
Output: 3

Constraints

  • 2 <= row, col <= 2 * 10^4
  • 4 <= row * col <= 2 * 10^4
  • cells.length == row * col
  • 1 <= ri <= row
  • 1 <= ci <= col
  • all the values of cells are unique

Hints for Last Day Where You Can Still Cross

  1. Hint 1

    If you can cross on day d, you can cross on every earlier day — fewer cells are flooded. So the answer is a threshold; binary search with a BFS per probe works.

  2. Hint 2

    Alternatively, run time backwards: start from an all-water grid and turn cells back into land from the last day to the first.

  3. Hint 3

    With a union-find plus two virtual nodes (top row, bottom row), the first moment going backwards that they become connected, after restoring cells[i], means day i is the last crossable day.

How to solve Last Day Where You Can Still Cross

Flooding only removes land, which breaks connectivity; reversing time turns it into adding land, which only merges components — exactly what union-find does well. Two virtual nodes stand for "the top row" and "the bottom row".

Approach

  1. Create a union-find over the row · col cells plus a TOP and a BOTTOM node; start with every cell flooded.
  2. For i from row · col - 1 down to 0: turn cells[i] into land, union it with TOP if it is in the first row, with BOTTOM if in the last row, and with every neighbouring land cell.
  3. As soon as TOP and BOTTOM share a root, return i: on day i exactly the cells cells[i..] are land.

Why it works

On day d the land is exactly cells[d], cells[d+1], …. Restoring cells in reverse order rebuilds those land sets for d = n - 1, n - 2, …, and a top-to-bottom walk exists iff TOP and BOTTOM are in one component. Since crossability is monotone in d, the first d met in this backward scan with a crossing is the largest such day.

Complexity

  • Time — O(row · col · α(row · col))
  • Space — O(row · col)

Pitfalls

  • Coordinates in cells are 1-based.
  • Moves are 4-directional; diagonal land does not connect.
  • Return the day, not the index of the cell that completed the crossing plus one: restoring cells[i] gives the land of day i.

Reference solution

Python

from typing import List

def latestDayToCross(row: int, col: int, cells: List[List[int]]) -> int:
    total = row * col
    top, bottom = total, total + 1
    parent = list(range(total + 2))
    land = [False] * total

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

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

    for i in range(total - 1, -1, -1):
        r, c = cells[i][0] - 1, cells[i][1] - 1
        x = r * col + c
        land[x] = True
        if r == 0:
            union(x, top)
        if r == row - 1:
            union(x, bottom)
        for a, b in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= a < row and 0 <= b < col and land[a * col + b]:
                union(x, a * col + b)
        if find(top) == find(bottom):
            return i
    return 0

Java

static int[] par;

static int find(int x) {
    while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
    return x;
}

static void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) par[ra] = rb;
}

public static int latestDayToCross(int row, int col, int[][] cells) {
    int total = row * col, top = total, bottom = total + 1;
    par = new int[total + 2];
    for (int i = 0; i < total + 2; i++) par[i] = i;
    boolean[] land = new boolean[total];
    int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
    for (int k = total - 1; k >= 0; k--) {
        int r = cells[k][0] - 1, c = cells[k][1] - 1, x = r * col + c;
        land[x] = true;
        if (r == 0) union(x, top);
        if (r == row - 1) union(x, bottom);
        for (int d = 0; d < 4; d++) {
            int a = r + DR[d], b = c + DC[d];
            if (a >= 0 && a < row && b >= 0 && b < col && land[a * col + b]) union(x, a * col + b);
        }
        if (find(top) == find(bottom)) return k;
    }
    return 0;
}

C++

vector<int> par;

int findRoot(int x) {
    while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
    return x;
}

void unite(int a, int b) {
    int ra = findRoot(a), rb = findRoot(b);
    if (ra != rb) par[ra] = rb;
}

int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
    int total = row * col, top = total, bottom = total + 1;
    par.assign(total + 2, 0);
    for (int i = 0; i < total + 2; i++) par[i] = i;
    vector<char> land(total, 0);
    int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
    for (int k = total - 1; k >= 0; k--) {
        int r = cells[k][0] - 1, c = cells[k][1] - 1, x = r * col + c;
        land[x] = 1;
        if (r == 0) unite(x, top);
        if (r == row - 1) unite(x, bottom);
        for (int d = 0; d < 4; d++) {
            int a = r + DR[d], b = c + DC[d];
            if (a >= 0 && a < row && b >= 0 && b < col && land[a * col + b]) unite(x, a * col + b);
        }
        if (findRoot(top) == findRoot(bottom)) return k;
    }
    return 0;
}

JavaScript

var latestDayToCross = function(row, col, cells) {
    var total = row * col, top = total, bottom = total + 1;
    var parent = [], land = [];
    for (var i = 0; i < total + 2; i++) { parent.push(i); land.push(false); }
    var find = function(x) {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    };
    var union = function(a, b) {
        var ra = find(a), rb = find(b);
        if (ra !== rb) parent[ra] = rb;
    };
    var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
    for (var k = total - 1; k >= 0; k--) {
        var r = cells[k][0] - 1, c = cells[k][1] - 1, x = r * col + c;
        land[x] = true;
        if (r === 0) union(x, top);
        if (r === row - 1) union(x, bottom);
        for (var d = 0; d < 4; d++) {
            var a = r + DR[d], b = c + DC[d];
            if (a >= 0 && a < row && b >= 0 && b < col && land[a * col + b]) union(x, a * col + b);
        }
        if (find(top) === find(bottom)) return k;
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)