Last Day Where You Can Still Cross - Practice Coding Problems

Last Day Where You Can Still Cross - Problem

Array Binary Search Depth-First Search Breadth-First Search Union Find Matrix Hard

There is a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively.

Initially on day 0, the entire matrix is land. However, each day a new cell becomes flooded with water. You are given a 1-based 2D array cells, where cells[i] = [ri, ci] represents that on the ith day, the cell on the rith row and cith column (1-based coordinates) will be covered with water (i.e., changed to 1).

You want to find the last day that it is possible to walk from the top to the bottom by only walking on land cells. You can start from any cell in the top row and end at any cell in the bottom row. You can only travel in the four cardinal directions (left, right, up, and down).

Return the last day where it is possible to walk from the top to the bottom by only walking on land cells.

Input & Output

Example 1 — Basic Grid

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

› Output: 2

💡 Note: Day 0: All land, path exists. Day 1: (1,1) flooded, path exists via (1,2)→(2,2). Day 2: (2,1) flooded, path exists via (1,2)→(2,2). Day 3: (1,2) flooded, no path from top to bottom.

Example 2 — Narrow Path

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

› Output: 1

💡 Note: Day 0: All land. Day 1: (1,1) flooded, path via (1,2)→(2,2). Day 2: (1,2) flooded, no path from top row to bottom row.

Example 3 — Large Grid

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

› Output: 3

💡 Note: Larger grid allows more flooding before path is completely blocked between top and bottom rows.

Constraints

2 ≤ row, col ≤ 2 × 10⁴
4 ≤ row × col ≤ 2 × 10⁴
cells.length == row × col
1 ≤ ri ≤ row
1 ≤ ci ≤ col
All the values of cells are unique.

Visualization

Tap to expand

Understanding the Visualization

Initial State

All cells are land (0), path exists from any top to any bottom

Daily Flooding

Each day one cell becomes water (1) according to cells array

Path Checking

Find last day when path still exists from top row to bottom row

Key Takeaway

🎯 Key Insight: Use binary search on days + BFS to efficiently find the last valid crossing day

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use binary search on the answer space combined with BFS/DFS for path verification. Instead of checking each day sequentially, we can binary search on the number of days and verify connectivity efficiently. Best approach is Binary Search + BFS with Time: O(log n × row × col), Space: O(row × col).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(log n × row × col)	O(row × col)	Binary search on days with BFS/DFS verification
Brute Force - Linear Day Check	O(n² × row × col)	O(row × col)	Check each day sequentially until path is blocked

Binary Search on Answer — Algorithm Steps

Step 1: Set search range from 0 to len(cells)
Step 2: For mid day, check if path exists using BFS
Step 3: Adjust search range based on path existence

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Range

Search between day 0 and max days

Test Mid

Check if path exists at middle day

Narrow Range

Adjust range based on result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int r, c;
} Point;

typedef struct {
    Point* data;
    int front, rear, size, capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* q = malloc(sizeof(Queue));
    q->data = malloc(capacity * sizeof(Point));
    q->front = q->rear = q->size = 0;
    q->capacity = capacity;
    return q;
}

void enqueue(Queue* q, Point p) {
    q->data[q->rear] = p;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
}

Point dequeue(Queue* q) {
    Point p = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return p;
}

bool canCross(int row, int col, int cells[][2], int cellCount, int day) {
    int** grid = malloc(row * sizeof(int*));
    bool** visited = malloc(row * sizeof(bool*));
    for (int i = 0; i < row; i++) {
        grid[i] = calloc(col, sizeof(int));
        visited[i] = calloc(col, sizeof(bool));
    }
    
    for (int i = 0; i < day; i++) {
        grid[cells[i][0] - 1][cells[i][1] - 1] = 1;  // Convert to 0-indexed
    }
    
    Queue* queue = createQueue(row * col);
    
    // Add all top row land cells
    for (int c = 0; c < col; c++) {
        if (grid[0][c] == 0) {
            Point p = {0, c};
            enqueue(queue, p);
            visited[0][c] = true;
        }
    }
    
    int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    while (queue->size > 0) {
        Point curr = dequeue(queue);
        
        if (curr.r == row - 1) {  // Reached bottom row
            // Free memory
            for (int i = 0; i < row; i++) {
                free(grid[i]);
                free(visited[i]);
            }
            free(grid);
            free(visited);
            free(queue->data);
            free(queue);
            return true;
        }
        
        for (int i = 0; i < 4; i++) {
            int nr = curr.r + directions[i][0];
            int nc = curr.c + directions[i][1];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col && !visited[nr][nc] && grid[nr][nc] == 0) {
                visited[nr][nc] = true;
                Point p = {nr, nc};
                enqueue(queue, p);
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < row; i++) {
        free(grid[i]);
        free(visited[i]);
    }
    free(grid);
    free(visited);
    free(queue->data);
    free(queue);
    return false;
}

int solution(int row, int col, int cells[][2], int cellCount) {
    int left = 0, right = cellCount;
    int result = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canCross(row, col, cells, cellCount, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    int row, col;
    scanf("%d", &row);
    scanf("%d", &col);
    
    char line[10000];
    scanf(" %s", line);
    
    // Parse 2D array - simplified parsing
    int cells[1000][2];
    int cellCount = 0;
    
    char* ptr = line + 1;  // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            cells[cellCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;  // Skip comma
            cells[cellCount][1] = atoi(ptr);
            cellCount++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
            if (*ptr == ',') ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(row, col, cells, cellCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n × row × col)

Binary search runs log n times, each with BFS taking O(row × col)

⚡ Linearithmic

Space Complexity

O(row × col)

Grid storage and BFS visited array

✓ Linear Space

18.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler