# Disconnect Path in a Binary Matrix by at Most One Flip
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip)
Canonical: https://scaleengineer.com/dsa/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
---
## 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:**

![](https://assets.glich.co/dsa/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/image0.png) 

**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:**

![](https://assets.glich.co/dsa/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/image1.png) 

**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.length`
* `n == grid[i].length`
* `1 <= m, n <= 1000`
* `1 <= m * n <= 105`
* `grid[i][j]` is either `0` or `1`.
* `grid[0][0] == grid[m - 1][n - 1] == 1`

# Approaches
## Brute Force by Iterating Through All Flips
This approach directly simulates the process described in the problem. It first checks if the grid is already disconnected. If not, it systematically tries flipping every possible '1' cell (excluding the start and end points) to a '0', one by one. After each flip, it re-evaluates if a path exists from `(0, 0)` to `(m-1, n-1)`. If any single flip results in a disconnected path, the function returns `true`. If all possible flips are tested and none work, it returns `false`.
**Time:** O((m*n)^2) - The grid has `m*n` cells. In the worst case, we iterate through `O(m*n)` cells. For each potential flip, we run a DFS/BFS which takes `O(m*n)` time, leading to a quadratic time complexity. · **Space:** O(m * n) - The space is dominated by the `visited` array or the recursion stack used in the DFS/BFS pathfinding helper function.
**Pros:** Simple to understand and implement.; Directly follows the logic of the problem statement.
**Cons:** Extremely inefficient due to its high time complexity.; Will likely result in a 'Time Limit Exceeded' error on larger grids, as it recomputes pathfinding from scratch for every potential flip.
### Explanation
The core of this method is a nested loop that iterates over every cell of the grid, combined with a pathfinding helper function (e.g., DFS). 

First, a baseline check is performed: is there a path from `(0, 0)` to `(m-1, n-1)` in the original grid? If not, we don't need to flip anything, and the answer is `true`.

If the grid is initially connected, the algorithm proceeds to test every flippable cell. For each cell `(i, j)` containing a `1` (and not being the start or end cell), it performs the following steps:
1.  **Flip**: Change `grid[i][j]` from `1` to `0`.
2.  **Check**: Run the pathfinding algorithm (DFS/BFS) to see if `(m-1, n-1)` is still reachable from `(0, 0)`.
3.  **Decide**: If the path is now broken, we have found a solution. Return `true`.
4.  **Restore**: If the path still exists, change `grid[i][j]` back to `1`. This is essential to ensure that we only test the effect of a single flip at a time.

If the algorithm iterates through all possible cells and fails to disconnect the path, it concludes that it's not possible and returns `false`.

```java
class Solution {
    private int m, n;
    private int[][] dirs = {{0, 1}, {1, 0}};

    public boolean isPossibleToCutPath(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;

        // 1. Check if path exists initially
        if (!hasPath(grid)) {
            return true;
        }

        // 2. Iterate and flip each valid cell
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Cannot flip start or end cells
                if ((i == 0 && j == 0) || (i == m - 1 && j == n - 1)) {
                    continue;
                }

                if (grid[i][j] == 1) {
                    grid[i][j] = 0; // Flip
                    if (!hasPath(grid)) {
                        return true; // Found a flip that disconnects
                    }
                    grid[i][j] = 1; // Flip back
                }
            }
        }

        return false;
    }

    private boolean hasPath(int[][] grid) {
        boolean[][] visited = new boolean[m][n];
        return dfs(grid, 0, 0, visited);
    }

    private boolean dfs(int[][] grid, int r, int c, boolean[][] visited) {
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
            return false;
        }
        if (r == m - 1 && c == n - 1) {
            return true;
        }

        visited[r][c] = true;

        for (int[] dir : dirs) {
            if (dfs(grid, r + dir[0], c + dir[1], visited)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Define a helper function, `hasPath(grid)`, which uses a pathfinding algorithm like Depth First Search (DFS) or Breadth First Search (BFS) to check for a path from `(0, 0)` to `(m-1, n-1)`. It returns `true` if a path exists, `false` otherwise.
- First, call `hasPath(grid)` on the original grid. If it returns `false`, the grid is already disconnected, so we can return `true`.
- If a path exists, iterate through each cell `(i, j)` of the grid.
- Skip the iteration if the cell is the start `(0, 0)` or the end `(m-1, n-1)`, as these cannot be flipped.
- If `grid[i][j]` is `1`:
    a. Temporarily flip the cell's value by setting `grid[i][j] = 0`.
    b. Call `hasPath(grid)` again on the modified grid.
    c. If `hasPath` returns `false`, it means this single flip successfully disconnected the path. We can immediately return `true`.
    d. **Crucially**, restore the grid by setting `grid[i][j] = 1` to undo the flip before checking the next cell.
- If the loops complete without finding any flip that disconnects the path, it's impossible. Return `false`.

## Two-Pass Traversal (Optimal)
This optimal approach leverages a key insight from graph theory on grid-based Directed Acyclic Graphs (DAGs). A path can be disconnected by flipping one cell if and only if there exists a 'bottleneck' cell that all paths from start to end must pass through. Such a bottleneck can be found by identifying an anti-diagonal line (`r + c = constant`) that contains only a single cell that is part of any valid path. The algorithm uses two traversals (one from the start and one from the end) to identify all cells that can possibly be on a path and then checks each anti-diagonal for such a bottleneck.
**Time:** O(m * n) - The algorithm performs a constant number of traversals (at most two) over the grid. Each traversal (DFS/BFS) visits each cell at most once, resulting in a linear time complexity with respect to the number of cells. · **Space:** O(m + n) or O(m*n) - The space complexity depends on the implementation. The conceptual approach with two boolean matrices uses `O(m*n)` space. The provided optimized code modifies the grid in-place and relies on the recursion stack for DFS, which in the worst case (a snake-like path) can be `O(m+n)`. If the grid is dense, the recursion could touch many cells, approaching `O(m*n)` in some scenarios.
**Pros:** Highly efficient with optimal time complexity.; Solves the problem with a fixed number of passes over the grid, regardless of its content.
**Cons:** The logic is more complex and less intuitive than the brute-force approach.; Requires extra space for two boolean matrices to store reachability information.
### Explanation
This method avoids re-computation by first gathering all necessary information in two passes and then analyzing it.

1.  **Forward Pass**: A single DFS/BFS is run from `(0, 0)`, moving only right and down. It populates a boolean matrix `reachableFromStart`, where `reachableFromStart[i][j]` is true if cell `(i, j)` is reachable from `(0, 0)`. If `(m-1, n-1)` is not reachable after this pass, the grid is already disconnected, and we return `true`.

2.  **Backward Pass**: A second DFS/BFS is run, this time starting from `(m-1, n-1)` and moving backward (up and left). This populates a `reachableFromEnd` matrix, where `reachableFromEnd[i][j]` is true if `(m-1, n-1)` is reachable from `(i, j)`.

After these two passes, a cell `(i, j)` is on at least one valid path if and only if `reachableFromStart[i][j]` and `reachableFromEnd[i][j]` are both true.

3.  **Bottleneck Analysis**: The final step is to check for a bottleneck. The number of vertex-disjoint paths in a grid DAG is equal to the minimum number of path-traversable nodes on any anti-diagonal. If this minimum is 1, we can disconnect the grid. We iterate through each intermediate anti-diagonal (from `r+c=1` to `r+c=m+n-3`) and count how many cells on it are part of a path. If we find any diagonal with a count of exactly 1, we've found our bottleneck, and we can return `true`.

If all diagonals have 0 or 2+ such cells, no single flip can disconnect the grid, so we return `false`.

```java
class Solution {
    private int m, n;

    public boolean isPossibleToCutPath(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;

        // 1. Forward pass: Check reachability from (0,0)
        if (!dfs(grid, 0, 0)) {
            // If one path doesn't exist, there can't be two.
            // This means we can disconnect by flipping one cell (or none if already disconnected).
            return true;
        }

        // Block the path found by the first DFS.
        // The first DFS, by its nature, finds one path and marks it with 0s.
        // (0,0) is reset to 1 so the second search can start.
        grid[0][0] = 1;

        // 2. Second pass: Check if another path exists
        // If another path exists, it means there are at least two disjoint paths.
        if (dfs(grid, 0, 0)) {
            return false; // Two disjoint paths exist, cannot disconnect with one flip.
        }

        return true; // Only one path (or path-family) exists, can be cut.
    }

    // DFS that returns true if path exists, and marks the path with 0s.
    private boolean dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return false;
        }

        if (r == m - 1 && c == n - 1) {
            return true;
        }

        // Mark current cell as visited by changing it to 0
        // This is a key trick: it blocks this cell for subsequent searches on the same path
        // and for the second major DFS call.
        if (r != 0 || c != 0) { // Don't block the start cell
            grid[r][c] = 0;
        }

        // Explore right and down
        if (dfs(grid, r + 1, c) || dfs(grid, r, c + 1)) {
            return true;
        }

        return false;
    }
}
```
*Note: The provided code snippet shows an even more concise implementation of the two-pass idea. The first DFS pass not only checks for a path but also destroys it by setting its cells to 0. If a second DFS can still find a path, it must be disjoint from the first, meaning disconnection is impossible. This avoids using extra space for `visited` arrays.*
### Algorithm
- Initialize two `m x n` boolean matrices, `reachableFromStart` and `reachableFromEnd`.
- Perform a forward traversal (DFS or BFS) from `(0, 0)` moving only right and down. Mark all reachable cells in `reachableFromStart`.
- Check if `reachableFromStart[m-1][n-1]` is `false`. If so, the grid is already disconnected, so return `true`.
- Perform a backward traversal (DFS or BFS) from `(m-1, n-1)` moving only up and left. Mark all cells from which the end is reachable in `reachableFromEnd`.
- Iterate through the intermediate anti-diagonals of the grid. An anti-diagonal is a set of cells `(r, c)` where `r + c = k`. We check for `k` from `1` to `m + n - 3`.
- For each anti-diagonal `k`:
    a. Initialize a counter `pathNodesOnDiagonal = 0`.
    b. For each cell `(r, c)` on this diagonal, check if it's part of any path by testing if `reachableFromStart[r][c]` and `reachableFromEnd[r][c]` are both true.
    c. If they are, increment `pathNodesOnDiagonal`.
    d. If `pathNodesOnDiagonal` for a given `k` is exactly `1`, it means we've found a bottleneck. Return `true`.
- If the loop finishes without finding any anti-diagonal with a count of `1`, it means no single-cell bottleneck exists. Return `false`.

# Solutions
### Java

```java
class Solution {
private
  int[][] grid;
private
  int m;
private
  int n;
public
  boolean isPossibleToCutPath(int[][] grid) {
    this.grid = grid;
    m = grid.length;
    n = grid[0].length;
    boolean a = dfs(0, 0);
    grid[0][0] = 1;
    grid[m - 1][n - 1] = 1;
    boolean b = dfs(0, 0);
    return !(a && b);
  }
private
  boolean dfs(int i, int j) {
    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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isPossibleToCutPath(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    function<bool(int, int)> dfs = [&](int i, int j) -> 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);
    };
    bool a = dfs(0, 0);
    grid[0][0] = grid[m - 1][n - 1] = 1;
    bool b = dfs(0, 0);
    return !(a && b);
  }
};

```

### Python

```python
class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool: def dfs(i, j): if i >= m or j >= n or grid[i][j] == 0: return False grid[i][j] = 0 if i == m - 1 and j == n - 1: return True return dfs(i + 1, j) or dfs(i, j + 1) m, n = len(grid), len(grid[0]) a = dfs(0, 0) grid[0][0] = grid[- 1][- 1] = 1 b = dfs(0, 0) return not (a and b)

```