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.
Perform a BFS or DFS from the starting point (0, 0) to determine if there is a path to (m-1, n-1). Record reachable cells. If these cells all remain connected even after a potential flip, then the grid cannot be disconnected. Otherwise, assess if flipping a single cell can break the connection.
The function uses a BFS to check if the grid is initially connected from (0, 0) to (m-1, n-1). If it is connected, the code then explores flipping each 0 cell adjacent to the connected path to determine if the grid can be disconnected by such a flip.
Python
JavaScript
Identify critical cells that are necessary for maintaining a path from (0, 0) to (m-1, n-1). Implement union-find to manage connectivity dynamically, and then flip cells to test disconnection potential while keeping track of reachability separately.
This C++ solution introduces a function to assess path existence via BFS, and tries flipping all 0s to check disconnection result. The logic is parallel to the BFS approach deconstructed earlier but refactored into modular functions suitable for C++ patterns.
First, we perform a DFS traversal to determine whether there is a path from (0, 0) to (m - 1, n - 1), and we denote the result as a. During the DFS process, we set the value of the visited cells to 0 to prevent revisiting.
Next, we set the values of (0, 0) and (m - 1, n - 1) to 1, and perform another DFS traversal to determine whether there is a path from (0, 0) to (m - 1, n - 1), and we denote the result as b. During the DFS process, we set the value of the visited cells to 0 to avoid revisiting.
Finally, if both a and b are true, we return false, otherwise, we return true.
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns of the matrix, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| BFS/DFS to Check Initial Connectivity |
|
| Track Reachable and Critical Cells Separately |
|
| Two DFS Traversals | — |
| 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 |
Disconnect Path in a Binary Matrix by at Most One Flip | Biweekly Contest 97 | Leetcode • codingMohan • 2,044 views views
Watch 6 more video solutions →Practice Disconnect Path in a Binary Matrix by at Most One Flip with our built-in code editor and test cases.
Practice on FleetCode