LeetCode 2556 - Disconnect Path in a Binary Matrix by at Most One Flip

The problem is asking whether it is possible to disconnect a path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) in a binary matrix by flipping at most one cell from 1 to 0 or 0 to 1. A path only allows moves down or right into cells containing 1.

leetcodemediumarraydynamic-programmingdepth-first-searchbreadth-first-searchmatrix

LeetCode Problem 2556

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem is asking whether it is possible to disconnect a path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) in a binary matrix by flipping at most one cell from 1 to 0 or 0 to 1. A path only allows moves down or right into cells containing 1. The matrix is already guaranteed to have 1 in both (0, 0) and (m - 1, n - 1).

The input is an m x n binary matrix with up to 10^5 cells in total. The output is a boolean: true if it is possible to disconnect the matrix with one flip, and false otherwise.

Key constraints include that only one cell can be flipped, and the start and end cells cannot be flipped. The problem size hints that a brute-force attempt to try flipping every cell and checking connectivity would likely be too slow.

Important edge cases include small matrices (1x1 or 1xN), matrices that are already disconnected, and matrices where only critical cells control the unique path. Because movement is restricted to right and down, the number of unique paths may be limited, which is crucial to the optimal approach.

Approaches

Brute Force

A naive approach is to iterate over every cell (i, j) that is not (0, 0) or (m - 1, n - 1), flip its value, and then perform a DFS or BFS to see if (m - 1, n - 1) is still reachable from (0, 0). If we find a flip that disconnects the path, we return true. If none work, we return false.

While correct, this is too slow for large matrices. Each connectivity check is O(m * n), and flipping each cell would result in O(m * n * m * n) time in the worst case, which can reach 10^10 operations - clearly infeasible.

Optimal Approach

The key insight is that if there are two or more independent paths from start to end, removing one cell will not disconnect the matrix. Therefore, to disconnect with a single flip, the grid must have a unique path from (0, 0) to (m - 1, n - 1) where all intermediate cells are critical.

We can achieve this by performing two DFS/BFS traversals:

  1. Forward DFS from (0, 0) to record which cells are reachable.
  2. Backward DFS from (m - 1, n - 1) to record which cells can reach the end.

If there is a cell that is on every valid path (i.e., visited in both forward and backward traversal), then flipping it disconnects the path. We only need to check intermediate cells, not the start or end.

This approach works efficiently in O(m * n) time because each cell is processed at most twice.

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) Flip each cell and check connectivity
Optimal O(m * n) O(m * n) DFS/BFS from start and end to identify unique critical path

Algorithm Walkthrough

  1. Forward DFS: Start from (0, 0) and mark all cells reachable moving only down or right through cells with 1. Store results in a reachable_from_start matrix.
  2. Backward DFS: Start from (m - 1, n - 1) and mark all cells that can reach the end moving only up or left through cells with 1. Store results in a reachable_to_end matrix.
  3. Check critical cells: Iterate through all intermediate cells (i, j) excluding (0, 0) and (m - 1, n - 1). If reachable_from_start[i][j] and reachable_to_end[i][j] are both true, this cell lies on a unique path. If such a cell exists, flipping it disconnects the path, so return true.
  4. No critical cell found: If no intermediate cell is on the unique path, return false.

Why it works: The forward and backward traversals together identify all cells that are part of some path. A cell visited in both is critical. Since flipping one critical cell disconnects the unique path, checking all such cells guarantees correctness.

Python Solution

from typing import List

class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        # Forward DFS from (0,0)
        reachable_from_start = [[False]*n for _ in range(m)]
        reachable_from_start[0][0] = True
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    if i > 0 and reachable_from_start[i-1][j]:
                        reachable_from_start[i][j] = True
                    if j > 0 and reachable_from_start[i][j-1]:
                        reachable_from_start[i][j] = True
        
        # Backward DFS from (m-1,n-1)
        reachable_to_end = [[False]*n for _ in range(m)]
        reachable_to_end[m-1][n-1] = True
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if grid[i][j] == 1:
                    if i < m-1 and reachable_to_end[i+1][j]:
                        reachable_to_end[i][j] = True
                    if j < n-1 and reachable_to_end[i][j+1]:
                        reachable_to_end[i][j] = True
        
        # Check intermediate critical cells
        for i in range(m):
            for j in range(n):
                if (i == 0 and j == 0) or (i == m-1 and j == n-1):
                    continue
                if reachable_from_start[i][j] and reachable_to_end[i][j]:
                    return True
        return False

The Python code constructs two boolean matrices to track reachable cells from the start and cells that can reach the end. It iterates through the grid twice: once forward and once backward. Any intermediate cell that is part of both matrices is critical. Flipping it disconnects the path.

Go Solution

func isPossibleToCutPath(grid [][]int) bool {
    m, n := len(grid), len(grid[0])
    reachableFromStart := make([][]bool, m)
    reachableToEnd := make([][]bool, m)
    for i := 0; i < m; i++ {
        reachableFromStart[i] = make([]bool, n)
        reachableToEnd[i] = make([]bool, n)
    }
    
    reachableFromStart[0][0] = true
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                if i > 0 && reachableFromStart[i-1][j] {
                    reachableFromStart[i][j] = true
                }
                if j > 0 && reachableFromStart[i][j-1] {
                    reachableFromStart[i][j] = true
                }
            }
        }
    }
    
    reachableToEnd[m-1][n-1] = true
    for i := m-1; i >= 0; i-- {
        for j := n-1; j >= 0; j-- {
            if grid[i][j] == 1 {
                if i < m-1 && reachableToEnd[i+1][j] {
                    reachableToEnd[i][j] = true
                }
                if j < n-1 && reachableToEnd[i][j+1] {
                    reachableToEnd[i][j] = true
                }
            }
        }
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if (i == 0 && j == 0) || (i == m-1 && j == n-1) {
                continue
            }
            if reachableFromStart[i][j] && reachableToEnd[i][j] {
                return true
            }
        }
    }
    return false
}

The Go implementation mirrors Python but uses slices of slices for the boolean matrices. Iteration and bounds checks are handled explicitly, and the logic for marking reachable cells is identical.

Worked Examples

Example 1: [[1,1,1],[1,0,0],[1,1,1]]

Forward reachability:

T T T
T F F
T T T

Backward reachability:

T F F
F F F
T T T

Intermediate critical cell: (1,0) is both forward and backward reachable, so flipping it disconnects the path. Output: true.

Example 2: [[1,1,1],[1,0,1],[1,1,1]]

Forward reachability:

T T