Disconnect Path in a Binary Matrix by at Most One Flip solution and explanation
Google
6 more videos on this problem
Disconnect Path in a Binary Matrix by at Most One Flip | Biweekly Contest 97 | LeetcodecodingMohan · 9:14 · 2K views
2556. Disconnect Path in a Binary Matrix by at Most One Flip | LeetCodeDeep Tech · 10:32 · 1K views
2556. Disconnect Path in a Binary Matrix by at Most One Flip | Leetcode BiWeekly Contest 97 | DFSTech Courses · 8:18 · 867 views
2556. Disconnect Path in a Binary Matrix by at Most One Flip (Leetcode Hard)Programming Live with Larry · 28:17 · 669 views
【每日一题】LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One FlipHuifeng Guan · 26:15 · 480 views
Leetcode 2556. Disconnect Path in a Binary Matrix by at Most One FlipElite Code · 30:42 · 338 views
Disconnect Path in a Binary Matrix by at Most One Flip | Leetcode Biweekly Contest 97 | BFS, GraphExplore with Gyani · 15:01 · 337 views
The problem
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 either0or1.grid[0][0] == grid[m - 1][n - 1] == 1
Approach overview
Problem 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 1: BFS/DFS to Check Initial Connectivity
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.
def is_possible_to_disconnect(grid):
from collections import deque
m, n = len(grid), len(grid[0])
if grid[0][0] == 0 or grid[m-1][n-1] == 0:
return False
# BFS to see if there's an original path
def bfs():
q = deque([(0, 0)])
visited = set([(0, 0)])
while q:
x, y = q.popleft()
if (x, y) == (m-1, n-1):
return True
for dx, dy in [(1, 0), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and (nx, ny) not in visited:
visited.add((nx, ny))
q.append((nx, ny))
return False
if not bfs():
return True # Already disconnected
# Try flipping positions adjacent to the path
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
grid[i][j] = 1
if not bfs():
return True
grid[i][j] = 0
return Falsefunction isPossibleToDisconnect(grid) {
const m = grid.length, n = grid[0].length;
if (grid[0][0] === 0 || grid[m-1][n-1] === 0) return true;
function bfs() {
const queue = [[0, 0]];
const visited = new Set(["0,0"]);
while (queue.length > 0) {
const [x, y] = queue.shift();
if (x === m-1 && y === n-1) return true;
for (const [dx, dy] of [[1, 0], [0, 1]]) {
const nx = x + dx, ny = y + dy;
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] === 1 && !visited.has(`${nx},${ny}`)) {
visited.add(`${nx},${ny}`);
queue.push([nx, ny]);
}
}
}
return false;
}
if (!bfs()) return true;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
grid[i][j] = 1;
if (!bfs()) return true;
grid[i][j] = 0;
}
}
}
return false;
}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.
- Time Complexity: O(m * n), where m and n are rows and columns.
- Space Complexity: O(m * n), due to the queue and visited set.
Approach 2: Track Reachable and Critical Cells Separately
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.
import java.util.*;
public class DisconnectPath {
public static boolean checkInitialConnectivity(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
queue.offer(new int[]{0, 0});
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
if (x == m - 1 && y == n - 1) return true;
for (int[] dir : new int[][]{{1, 0}, {0, 1}}) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < m && ny < n && grid[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
return false;
}
public static boolean isPossibleToDisconnect(int[][] grid) {
int m = grid.length, n = grid[0].length;
if (!checkInitialConnectivity(grid)) return true;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
grid[i][j] = 1;
if (!checkInitialConnectivity(grid)) return true;
grid[i][j] = 0;
}
}
}
return false;
}
}#include <vector>
#include <queue>
using namespace std;
bool isPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
if (grid[0][0] == 0 || grid[m-1][n-1] == 0) return false;
queue<pair<int, int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
q.push({0, 0});
visited[0][0] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == m - 1 && y == n - 1) return true;
for (auto [dx, dy] : vector<pair<int, int>>{{1, 0}, {0, 1}}) {
int nx = x + dx, ny = y + dy;
if (nx < m && ny < n && grid[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
bool isPossibleToDisconnect(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
if (!isPath(grid)) return true;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
grid[i][j] = 1;
if (!isPath(grid)) return true;
grid[i][j] = 0;
}
}
}
return false;
}The Java solution separates the path-checking logic into a helper function to streamline the control flow. By seeing each step compartmentalized, its structure facilitates the handoff of logic across the main and helper methods, embracing standard Java practices.
- Time Complexity: O(m * n), with BFS evaluating each cell's connectivity once.
- Space Complexity: O(m * n), from queues/lists used to track cell exploration.
Approach 3: Two DFS Traversals
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.
function isPossibleToCutPath(grid: number[][]): boolean {
const m = grid.length;
const n = grid[0].length;
const dfs = (i: number, j: number): boolean => {
if (i >= m || j >= n || grid[i][j] !== 1) {
return false;
}
grid[i][j] = 0;
if (i === m - 1 && j === n - 1) {
return true;
}
return dfs(i + 1, j) || dfs(i, j + 1);
};
const a = dfs(0, 0);
grid[0][0] = 1;
grid[m - 1][n - 1] = 1;
const b = dfs(0, 0);
return !(a && b);
}func isPossibleToCutPath(grid [][]int) bool {
m, n := len(grid), len(grid[0])
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if i >= m || j >= n || grid[i][j] == 0 {
return false
}
if i == m-1 && j == n-1 {
return true
}
grid[i][j] = 0
return dfs(i+1, j) || dfs(i, j+1)
}
a := dfs(0, 0)
grid[0][0], grid[m-1][n-1] = 1, 1
b := dfs(0, 0)
return !(a && b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| BFS/DFS to Check Initial Connectivity |
|
| Track Reachable and Critical Cells Separately |
|
| Two DFS Traversals | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Disconnect Path in a Binary Matrix by at Most One Flip easy or hard?
This problem is rated Medium on LeetCode but feels tricky because it mixes grid traversal with reasoning about multiple paths. The implementation itself is straightforward once the insight about testing for a second independent path is understood.
Disconnect Path in a Binary Matrix by at Most One Flip Python/Java solution
Python and Java implementations typically use DFS or BFS for grid traversal. The algorithm first finds one path from start to end, blocks that path, and runs the search again. If the second search fails to reach the target, flipping one cell successfully disconnects the grid.
How to solve Disconnect Path in a Binary Matrix by at Most One Flip in O(m*n)?
First run DFS or BFS to check if a path from the top-left to bottom-right exists. If no path exists, return true. If a path exists, mark the cells of that path as blocked and run the traversal again. If the destination is still reachable, more than one independent path exists and one flip is insufficient; otherwise the grid becomes disconnected.
What is the best approach for Disconnect Path in a Binary Matrix by at Most One Flip?
The most practical approach uses DFS or BFS to find one valid path from the start to the end, temporarily removes that path, and then checks if another path still exists. If a second path is found, the grid cannot be disconnected with one flip. If no second path exists, flipping a cell from the first path breaks connectivity. This solution runs in O(m*n) time.
Is Disconnect Path in a Binary Matrix by at Most One Flip asked at Google/Amazon/Meta?
Grid traversal and path‑disconnection problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving DFS, BFS, or identifying critical cells in a grid are common because they test graph modeling and algorithmic reasoning.
What data structure is used in Disconnect Path in a Binary Matrix by at Most One Flip?
The core data structures are a matrix for the grid, a visited structure for traversal, and either a recursion stack (DFS) or queue (BFS). Some optimized solutions also use dynamic programming arrays to track cells reachable from the start and from the end.
What is the time complexity of Disconnect Path in a Binary Matrix by at Most One Flip?
Both common solutions run in O(m*n) time where m and n are the grid dimensions. The algorithm performs at most two full traversals of the matrix using DFS or BFS. Space complexity is also O(m*n) due to recursion stack or visited tracking structures.