#2556

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Disconnect Path in a Binary Matrix by at Most One Flip

Determine if a single cell flip can disconnect a path from the top-left to bottom-right in a binary matrix efficiently using DP and graph traversal.

array dynamic programming depth first search breadth first search matrix

Problem Statement

Given an m x n binary matrix grid, you can move from a cell (row, col) to (row + 1, col) or (row, col + 1) only if the destination cell contains 1. The matrix is considered disconnected if there is no path from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1).

You are allowed to flip at most one cell's value from 1 to 0 or 0 to 1, excluding the top-left and bottom-right cells. Return true if it is possible to disconnect the matrix with at most one flip, otherwise return false.

Examples

Example 1

Input: grid = [[1,1,1],[1,0,0],[1,1,1]]

Output: true

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

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

Solution Approach

Forward and Backward Reachability

Use DFS or BFS to compute reachability from the start cell to every other cell and from the end cell backward. Identify cells that are on all possible paths. These cells are candidates whose flip may disconnect the matrix.

State Transition Dynamic Programming

Implement a DP table tracking if each cell is reachable from the start and from the end. Combine these states to detect critical cells where a flip would break all paths, leveraging the matrix as a graph.

Single Flip Evaluation

Iterate over critical cells and simulate flipping each one. If flipping any of them results in no path between start and end, return true. Otherwise, after checking all candidates, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on performing two full traversals of the grid for reachability, plus iterating over potential critical cells, yielding roughly O(m * n). Space complexity is O(m * n) for the DP tables and recursion/queue structures.

What Interviewers Usually Probe

Ask about handling large grids efficiently using DP instead of exhaustive path enumeration.
Probe knowledge of critical path identification in state transition DP for matrices.
Check understanding of combining forward and backward traversal for minimal flips.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude the top-left and bottom-right cells from possible flips.
Failing to identify cells that are truly critical to all paths, leading to incorrect disconnection checks.
Using BFS/DFS without DP may result in excessive time complexity for large grids.

Follow-up variants

Allow flipping multiple cells and determine the minimum number needed to disconnect the path.
Consider diagonal moves along with right and down for more complex connectivity.
Determine the maximum number of disjoint paths that remain after one flip.

FAQ

What does "Disconnect Path in a Binary Matrix by at Most One Flip" require in terms of algorithmic approach?

It requires identifying critical cells via state transition dynamic programming combined with DFS/BFS to check if flipping a single cell can disconnect the path.

Can I flip the start or end cell to disconnect the matrix?

No, flipping (0, 0) or (m - 1, n - 1) is not allowed; only internal cells can be considered for disconnection.

Is a full path enumeration necessary for this problem?

No, forward and backward reachability with DP efficiently identifies critical cells without enumerating all paths.

What grid sizes are feasible with this approach?

The DP and BFS/DFS approach works efficiently for grids up to 1000 x 1000, leveraging O(m * n) time and space.

How does state transition DP help in this problem?

It tracks which cells are reachable from both start and end, allowing identification of cells whose flip can disconnect all paths, minimizing unnecessary traversal.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)

Continue Practicing

#2328 number of increasing paths in a grid #2617 minimum number of visited cells in a grid #1970 last day where you can still cross