Problem statement

You are given an m x n binary matrix grid. From a cell (row, col) you may move only to (row + 1, col) or (row, col + 1), and only onto cells holding 1.

The matrix is disconnected if there is no such path from (0, 0) to (m - 1, n - 1).

You may flip at most one cell (change a 0 to 1 or a 1 to 0), but you may not flip (0, 0) or (m - 1, n - 1).

Return true if the matrix can be made disconnected, and false otherwise.

Example 1

Input: grid = [[1,1,1],[1,0,0],[1,1,1]]
Output: true
Explanation: The top row is a dead end because (1,2) is 0, so every path goes down through (1,0). Flipping (1,0) to 0 cuts them all.

Example 2

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: false
Explanation: The top-right route and the bottom-left route share no cell besides the corners, so no single flip cuts both.

Example 3

Input: grid = [[1]]
Output: false
Explanation: Start and end are the same cell, which may not be flipped.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 10^5
• grid[i][j] is either 0 or 1
• grid[0][0] == grid[m - 1][n - 1] == 1

Hints for Disconnect Path in a Binary Matrix by at Most One Flip

1. Hint 1

   Turning a 0 into a 1 never disconnects anything, so the only useful flip removes a cell that lies on a path.

2. Hint 2

   Every right/down path visits exactly one cell on each anti-diagonal i + j = d. Mark the cells that are both reachable from the start and able to reach the end.

3. Hint 3

   If some anti-diagonal strictly between the corners holds exactly one such cell, every path goes through it — flip it. (If no path exists at all, the answer is already true.)

How to solve Disconnect Path in a Binary Matrix by at Most One Flip

A monotone path takes exactly one step from anti-diagonal d to d + 1, so it meets every anti-diagonal exactly once. The cells usable by some path are those reachable from (0, 0) that can also reach (m - 1, n - 1). If an intermediate anti-diagonal contains a single usable cell, that cell is on every path; flipping it disconnects the grid. If every intermediate anti-diagonal has two or more, no one cell blocks everything.

Approach

1. Forward DP: f[i][j] is true when grid[i][j] == 1 and (i, j) is the start or f holds above or to the left.
2. Backward DP: g[i][j] is true when grid[i][j] == 1 and (i, j) is the end or g holds below or to the right.
3. If f[m-1][n-1] is false the grid is already disconnected: return true.
4. Count usable cells (f && g) per anti-diagonal; return true if any d in 1 .. m + n - 3 has count 1, else false.

Why it works

If a diagonal has one usable cell, every start-to-end path passes through it, so removing it leaves none. Conversely, if every intermediate diagonal has at least two usable cells, the topmost and bottommost usable paths are vertex-disjoint apart from the corners (a standard Menger-type argument on this grid), so removing any single cell leaves one of them intact.

Complexity

• Time — O(mn)
• Space — O(mn)

Pitfalls

• Exclude the two corner diagonals (d = 0 and d = m + n - 2) — those cells cannot be flipped.
• A cell reachable from the start but unable to reach the end is not on any path; counting it hides a bottleneck.
• A grid with no path at all needs zero flips: answer true.

Reference solution

Python

from typing import List

def isPossibleToCutPath(grid: List[List[int]]) -> bool:
    m, n = len(grid), len(grid[0])
    f = [[False] * n for _ in range(m)]
    g = [[False] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                f[i][j] = (i == 0 and j == 0) or (i > 0 and f[i - 1][j]) or (j > 0 and f[i][j - 1])
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if grid[i][j] == 1:
                g[i][j] = (i == m - 1 and j == n - 1) or (i < m - 1 and g[i + 1][j]) or (j < n - 1 and g[i][j + 1])
    if not f[m - 1][n - 1]:
        return True
    cnt = [0] * (m + n - 1)
    for i in range(m):
        for j in range(n):
            if f[i][j] and g[i][j]:
                cnt[i + j] += 1
    return any(cnt[d] == 1 for d in range(1, m + n - 2))

Java

public static boolean isPossibleToCutPath(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    boolean[][] f = new boolean[m][n], g = new boolean[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == 1) f[i][j] = (i == 0 && j == 0) || (i > 0 && f[i - 1][j]) || (j > 0 && f[i][j - 1]);
    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--)
            if (grid[i][j] == 1) g[i][j] = (i == m - 1 && j == n - 1) || (i < m - 1 && g[i + 1][j]) || (j < n - 1 && g[i][j + 1]);
    if (!f[m - 1][n - 1]) return true;
    int[] cnt = new int[m + n - 1];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (f[i][j] && g[i][j]) cnt[i + j]++;
    for (int d = 1; d <= m + n - 3; d++) if (cnt[d] == 1) return true;
    return false;
}

C++

bool isPossibleToCutPath(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<char>> f(m, vector<char>(n, 0)), g(m, vector<char>(n, 0));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == 1) f[i][j] = (i == 0 && j == 0) || (i > 0 && f[i - 1][j]) || (j > 0 && f[i][j - 1]);
    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--)
            if (grid[i][j] == 1) g[i][j] = (i == m - 1 && j == n - 1) || (i < m - 1 && g[i + 1][j]) || (j < n - 1 && g[i][j + 1]);
    if (!f[m - 1][n - 1]) return true;
    vector<int> cnt(m + n - 1, 0);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (f[i][j] && g[i][j]) cnt[i + j]++;
    for (int d = 1; d <= m + n - 3; d++) if (cnt[d] == 1) return true;
    return false;
}

JavaScript

var isPossibleToCutPath = function(grid) {
    var m = grid.length, n = grid[0].length;
    var f = [], g = [];
    for (var i = 0; i < m; i++) { f.push([]); g.push([]); for (var j = 0; j < n; j++) { f[i].push(false); g[i].push(false); } }
    for (var a = 0; a < m; a++)
        for (var b = 0; b < n; b++)
            if (grid[a][b] === 1) f[a][b] = (a === 0 && b === 0) || (a > 0 && f[a - 1][b]) || (b > 0 && f[a][b - 1]);
    for (var c = m - 1; c >= 0; c--)
        for (var d = n - 1; d >= 0; d--)
            if (grid[c][d] === 1) g[c][d] = (c === m - 1 && d === n - 1) || (c < m - 1 && g[c + 1][d]) || (d < n - 1 && g[c][d + 1]);
    if (!f[m - 1][n - 1]) return true;
    var cnt = [];
    for (var k = 0; k < m + n - 1; k++) cnt.push(0);
    for (var x = 0; x < m; x++)
        for (var y = 0; y < n; y++)
            if (f[x][y] && g[x][y]) cnt[x + y]++;
    for (var t = 1; t <= m + n - 3; t++) if (cnt[t] === 1) return true;
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium