Solution: Last Day Where You Can Still Cross

Let's solve the Last Day Where You Can Still Cross problem using the Union Find pattern.

Statement

You are given two integers, rows and cols, which represent the number of rows and columns in a 1-based binary matrixA 1-based matrix has an indexing that starts from 1 instead of 0, and a binary matrix contains only binary values, i.e., 0 and 1. Therefore, a 1-based binary matrix is a matrix containing only 0s and 1s, whose indexes (for both rows and columns) start from 1.. In this matrix, each 00 represents land, and each 11 represents water.

Initially, on day 0, the whole matrix will just be all 0s, that is, all land. With each passing day, one of the cells of this matrix will get flooded and, therefore, will change to water, that is, from 00 to 11. This continues until the entire matrix is flooded. You are given a 1-based array, waterCells, that records which cell will be flooded on each day. Each element waterCells[i]=[ri,ci]waterCells[i] = [r_{i},c_{i}] indicates the cell present at the rith{r_{i}}^{th} row and cith{c_{i}}^{th} column of the matrix that will change from land to water on the ithi^{th} day.

We can cross any cell of the matrix as long as it’s land. Once it changes to water, we can’t cross it. To cross any cell, we can only move in one of the four cardinal directionsleft, right, up, and down. Given the number of rows and columns of a 1-based binary matrix and a 1-based array, waterCells, you are required to find the last day where you can still cross the matrix, from top to bottom, by walking over the land cells only.

Note: You can start from any cell in the top row, and you need to be able to reach just one cell in the bottom row for it to count as a crossing.

Constraints:

  • 22 \leq rows,, cols 2×104\leq 2 \times 10^4
  • 44 \leq rows ×\times cols 2×104\leq 2 \times 10^4
  • waterCells.length ==== rows ×\times cols
  • 1ri1 \leq r_{i} \leq rows
  • 1ci1 \leq c_{i} \leq cols
  • All values of waterCells are unique.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.