D
DevExCode

LeetCode 1970: Last Day Where You Can Still Cross Solution

Master LeetCode problem 1970 (Last Day Where You Can Still Cross), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use a binary search approach to find the last day where it is possible to walk from the top to the bottom by only walking on land cells. We will start with binary search range from 1 to the maximum possible day. For each day, we will simulate the flooding process and check if there exists a path from the top row to the bottom row using depth-first search (DFS). If a path exists, we update our binary search range accordingly.

The time complexity of this approach is O(logD * RC), where D is the number of days and RC is the total number of cells in the matrix. The space complexity is O(RC) for storing the flooded cells.

Solution Code

class Solution {
    public int latestDayToCross(int row, int col, int[][] cells) {
        int left = 1, right = row * col;
        int[][] grid = new int[row][col];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            for (int i = 0; i < mid; i++) {
                int r = cells[i][0] - 1;
                int c = cells[i][1] - 1;
                grid[r][c] = 1;
            }
            if (dfs(grid, 0, 0, row, col)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left - 1;
    }
    
    private boolean dfs(int[][] grid, int r, int c, int row, int col) {
        if (r < 0 || r >= row || c < 0 || c >= col || grid[r][c] == 1) {
            return false;
        }
        if (r == row - 1) {
            return true;
        }
        
        grid[r][c] = 1;
        boolean res = dfs(grid, r + 1, c, row, col)
            || dfs(grid, r, c + 1, row, col)
            || dfs(grid, r - 1, c, row, col)
            || dfs(grid, r, c - 1, row, col);
        
        return res;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1970 (Last Day Where You Can Still Cross)?

This page provides optimized solutions for LeetCode problem 1970 (Last Day Where You Can Still Cross) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1970 (Last Day Where You Can Still Cross)?

The time complexity for LeetCode 1970 (Last Day Where You Can Still Cross) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1970 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1970 in Java, C++, or Python.

Back to LeetCode Solutions