Disconnect Path in a Binary Matrix by at Most One Flip

Disconnect Path in a Binary Matrix by at Most One Flip

What is this problem about?

In the Disconnect Path in a Binary Matrix by at Most One Flip coding problem, you are given a binary grid where 1 represents a passable cell and 0 represents a wall. You can move only down or right from $(0,0)$ to $(m-1, n-1)$. You need to determine if it is possible to make the destination unreachable from the start by flipping at most one '1' cell (excluding the start and end).

Why is this asked in interviews?

Google uses this problem to test a candidate's understanding of Graph Connectivity and Critical Path analysis. It evaluations whether you can identify a "bottleneck" in a grid. If there is any point in time (any Manhattan distance from the start) where only one path exists, flipping that cell disconnects the graph. It’s a sophisticated test of grid traversal logic.

Algorithmic pattern used

There are two main ways to solve this:

1. Double DFS: Run one DFS to find any path to the end. Mark all cells on that path as 0 (except start and end). Then run a second DFS. If the second DFS cannot reach the end, it means the first path contained a bottleneck cell.
2. Breadth-First Search (BFS) by Distance: Count how many 1s exist at each distance $d = r + c$ from the start. If at any distance $d$ (other than 0 and $m+n-2$), there is only one reachable 1, that cell is a mandatory bridge. Flipping it will disconnect the path.

Example explanation

Grid:

1 1 1
1 0 1
1 1 1

Paths from (0,0) to (2,2):

• (0,0) $\to$ (0,1) $\to$ (0,2) $\to$ (1,2) $\to$ (2,2)
• (0,0) $\to$ (1,0) $\to$ (2,0) $\to$ (2,1) $\to$ (2,2) If we flip (0,1), the first path is gone, but the second remains. However, if all paths had to pass through (1,1) and we flipped it, the destination would be disconnected.

Common mistakes candidates make

• Only checking start/end: Forgetting that any cell in the middle can be a bottleneck.
• Inefficient path finding: Trying to count all possible paths ($O(2^{N+M})$), which is unnecessary and too slow.
• Misinterpreting "One Flip": Not realizing that if the path is already disconnected, the answer is true.

Interview preparation tip

For grid problems involving "reachability" and "moving only down/right," always think about the $r+c$ invariant. Elements with the same $r+c$ sum are at the same "step" from the start. If only one valid cell exists at a particular step, that cell is a critical bottleneck.