What is the time complexity of LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip?

The Python solution on this page uses O(m \times n) auxiliary space.

Disconnect Path in a Binary Matrix by at Most One Flip — LeetCode 2556 Python Solution

MediumDepth-First SearchBreadth-First SearchArrayDynamic ProgrammingMatrix

Problem: #2556
Pattern: Matrix and Grid
Reading time: 3 min
Source: leetcode.com

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.

Example

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.

Python solution

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)

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(m \times n) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip?: LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip is rated Medium on LeetCode.
What is the time complexity of LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip?: The Python solution on this page uses O(m \times n) auxiliary space.
What topics does LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip cover?: LeetCode 2556. Disconnect Path in a Binary Matrix by at Most One Flip is tagged Depth-First Search, Breadth-First Search, Array, Dynamic Programming and Matrix on LeetCode.