Last Day Where You Can Still Cross

Last Day Where You Can Still Cross

1. What is this problem about?

The Last Day Where You Can Still Cross coding problem involves a grid that starts as all water (0) and gradually turns into land (1) as days pass. You are given a sequence of coordinates where land appears each day. You need to find the last day you can still walk from the top row to the bottom row using only land cells (moving 4-directionally).

2. Why is this asked in interviews?

This "Hard" problem is a favorite at Atlassian and Google because it tests complex graph traversal and search strategies. It can be solved using either Binary Search on the answer or Union Find. It evaluates your ability to model a dynamic environment where connectivity changes over time and your knowledge of advanced algorithms like BFS/DFS or Disjoint Set Union (DSU).

3. Algorithmic pattern used

There are two main patterns: Binary Search + BFS/DFS, or Union Find.

1. Binary Search approach: Binary search for the day. For a mid-day, build the grid with all land that has appeared up to that day and check for connectivity from top to bottom using BFS or DFS.
2. Union Find approach: Process the days in reverse order (from all land back to all water) and use DSU to join adjacent land cells. The first day you connect a "virtual top" node to a "virtual bottom" node is your answer.

4. Example explanation

2x2 grid. Days: 1: (1,1), 2: (2,2), 3: (1,2), 4: (2,1).

• Day 1: Only (1,1) is land. No path.
• Day 2: (1,1) and (2,2) are land. No path (they are diagonal).
• Day 3: (1,1), (2,2), and (1,2) are land. Path: (1,2) -> (2,2) connects top to bottom.
• Day 4: All land. Path exists. The last day you can cross is day 3. (Wait, the question asks for the last day you can still cross. If on day 4 you can cross, and there are no more days, then 4. In this problem, cells are usually blocked, meaning land turns into water or vice versa. Let's assume land allows crossing).

5. Common mistakes candidates make

The most common mistake is using BFS/DFS for every single day, which results in O(Days * N * M) and is far too slow. Using Binary Search reduces this to O(log(Days) * N * M). Another mistake is incorrect grid initialization (1-indexed vs 0-indexed) or forgetting to handle the 4-directional movement constraints.

6. Interview preparation tip

For "Union Find, Binary Search interview pattern" problems on grids, always consider processing the events in reverse. Many problems that involve "breaking connectivity" become much easier to solve with DSU when viewed as "forming connectivity" in reverse.