1970. Last Day Where You Can Still Cross
Approach
Binary search on day; BFS/DFS to check if top-to-bottom path exists with flooded cells.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
// Approach: Binary search on day; BFS/DFS to check if top-to-bottom path exists with flooded cells.
// Time: O(mn log(mn)) Space: O(mn)
public class Solution
{
private int[][] cells;
private int rows;
private int cols;
public int LatestDayToCross(int row, int col, int[][] cells)
{
this.cells = cells;
this.rows = row;
this.cols = col;
// Binary search for first day where crossing becomes impossible
int left = 1;
int right = cells.Length;
int firstTrueIndex = -1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (Feasible(mid))
{
firstTrueIndex = mid;
right = mid - 1;
}
else
left = mid + 1;
}
// Return last day where crossing was still possible
return firstTrueIndex - 1;
}
private bool Feasible(int day)
{
// Returns true when crossing is NOT possible (inverted condition)
return !CanCross(day);
}
private bool CanCross(int dayCount)
{
int[,] grid = new int[rows, cols];
for (int i = 0; i < dayCount; i++)
grid[cells[i][0] - 1, cells[i][1] - 1] = 1;
int[] directions = { -1, 0, 1, 0, -1 };
Queue<(int, int)> queue = new Queue<(int, int)>();
for (int c = 0; c < cols; c++)
{
if (grid[0, c] == 0)
{
queue.Enqueue((0, c));
grid[0, c] = 1;
}
}
while (queue.Count > 0)
{
var (currentRow, currentCol) = queue.Dequeue();
if (currentRow == rows - 1)
return true;
for (int i = 0; i < 4; i++)
{
int nextRow = currentRow + directions[i];
int nextCol = currentCol + directions[i + 1];
if (nextRow >= 0 && nextRow < rows &&
nextCol >= 0 && nextCol < cols &&
grid[nextRow, nextCol] == 0)
{
queue.Enqueue((nextRow, nextCol));
grid[nextRow, nextCol] = 1;
}
}
}
return false;
}
}