Watch 7 video solutions for Disconnect Path in a Binary Matrix by at Most One Flip, a medium level problem involving Array, Dynamic Programming, Depth-First Search. This walkthrough by codingMohan has 2,044 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1) that has the value 1. The matrix is disconnected if there is no path from (0, 0) to (m - 1, n - 1).
You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m - 1, n - 1).
Return true if it is possible to make the matrix disconnect or false otherwise.
Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.
Example 1:
Input: grid = [[1,1,1],[1,0,0],[1,1,1]] Output: true Explanation: We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.
Example 2:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]] Output: false Explanation: It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 105grid[i][j] is either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 1Problem Overview: You are given a binary matrix where 1 represents a valid cell and 0 represents a blocked cell. Starting from the top‑left corner, you can only move right or down. The task is to determine whether flipping at most one 1 to 0 can disconnect all paths from the start cell to the bottom‑right cell.
Approach 1: BFS/DFS to Check and Remove One Path (O(m*n) time, O(m*n) space)
Run a DFS or BFS from (0,0) to see if a valid path to (m-1,n-1) exists. If no path exists, the grid is already disconnected, so return true. Otherwise, trace one discovered path and temporarily flip its intermediate cells to 0. Then run the traversal again. If another path still reaches the destination, the grid cannot be disconnected with a single flip. If no second path exists, one flipped cell along the original path is enough to break connectivity.
The key insight: if two independent paths exist that do not rely on the same intermediate cell, removing one cell will not disconnect the grid. Removing the cells of the first discovered path tests whether an alternative route exists. This technique relies heavily on grid traversal using Depth-First Search or Breadth-First Search.
Approach 2: Track Reachable and Critical Cells Separately (Dynamic Programming) (O(m*n) time, O(m*n) space)
Compute reachability from the start and from the end separately. A forward DP or BFS marks cells reachable from (0,0), while a reverse traversal marks cells that can reach (m-1,n-1). Any cell that appears in both sets lies on at least one valid path.
Next, count how many such cells appear on each "layer" defined by i + j. If a layer contains exactly one reachable cell that lies on every path, that cell becomes a critical bottleneck. Flipping it disconnects the grid. This method effectively identifies articulation-like points in the path structure using Dynamic Programming on a matrix.
Recommended for interviews: The DFS/BFS path-removal approach is the most common interview solution. It is simple, runs in O(m*n), and demonstrates strong understanding of grid traversal and path uniqueness. The DP reachability method shows deeper insight into path structure and critical cells but is slightly harder to reason about under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS/BFS Path Detection and Removal | O(m*n) | O(m*n) | General interview solution; simple traversal and easy to implement |
| Reachability + Critical Layer Tracking (DP) | O(m*n) | O(m*n) | When analyzing path bottlenecks or identifying critical cells across all paths |