Disconnect Path In A Binary Matrix By At Most One Flip - Leetcode Solution

The problem statement can be found on Leetcode here: https://leetcode.com/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/

Given a binary matrix mat, we need to find if we can disconnect the path of 1s from the top of the matrix to the bottom, by flipping at most one 0 to 1. The path of 1s can only have horizontal or vertical direction changes, not diagonal.

For example, consider the following input matrix:

mat = [[1,1,0,0],
       [1,0,0,1],
       [0,1,1,1],
       [1,0,1,0]]

The path of 1s starts from (0,0) and goes down to reach (3,0), then it turns right to reach (3,2) and finally goes down again to reach (3,3). In order to disconnect this path, we can flip the 0 at position (1,2) to make it 1. The updated matrix would be:

mat = [[1,1,0,0],
       [1,0,1,1],  # This 0 has been flipped to 1
       [0,1,1,1],
       [1,0,1,0]]

Now, the path of 1s can no longer go from (0,0) to (3,0) without passing through a 0.

A key observation for this problem is that since we can only flip at most one 0, the disconnected path can only have one "endpoint". That is, there can be at most one cell in the path that has only one neighboring 1.

So one way to solve this problem is to explore all possible candidates for the "endpoint", and check if flipping any surrounding 0 can disconnect the path.

Let's see how we can implement this approach.

Algorithm:

1. For each cell (i,j) with value 1 and either i=0 or i=n-1 or j=0 or j=m-1 (i.e., it's a border cell), do the following:
2. Use Depth First Search (DFS) to explore all connected 1s from this cell, marking them as visited.
3. If during DFS we encounter a cell (x,y) with value 0 and exactly one neighboring 1 (x',y'), we have found a candidate for the "endpoint". Mark this cell as candidate and stop DFS.
4. After DFS finishes, if we have found a candidate, we need to check if flipping its 0 neighbor can disconnect the path.
5. For each neighbor (x',y') of candidate with value 0, do the following:

• Flip (x',y') to 1, and mark all cells reachable from candidate by DFS (excluiding (x',y')) as visited2.
• Check if there's a path of 1s from the top border to the bottom border that doesn't intersect visited2. If so, we can disconnect the path and return True.
• Otherwise, flip (x',y') back to 0, and continue to the next neighbor.

6. If we finished all candidates without finding a way to disconnect the path, return False.

Let's see the implementation:

n, m = len(mat), len(mat[0])
dirs = [(0,1),(0,-1),(1,0),(-1,0)]

# Check if there's a path of 1s from the top border to the bottom border
# that doesn't intersect visited2
def isConnected(visited2):
    for j in range(m):
        # Start DFS from top border
        if mat[0][j] == 1 and (0,j) not in visited2:
            stack = [(0,j)]
            while stack:
                i, j = stack.pop()
                if i == n-1: return False # Found a path that intersects visited2
                visited2.add((i,j))
                for di, dj in dirs:
                    ni, nj = i+di, j+dj
                    if 0<=ni<n and 0<=nj<m and mat[ni][nj] == 1 and (ni,nj) not in visited2:
                        stack.append((ni,nj))
    return True

# Check all candidates for endpoints
for i in range(n):
    for j in range(m):
        if mat[i][j] == 1 and (i==0 or i==n-1 or j==0 or j==m-1):
            visited, candidate = set(), None
            stack = [(i,j)]
            while stack:
                i, j = stack.pop()
                if (i,j) in visited: continue
                visited.add((i,j))
                ones = []
                for di, dj in dirs:
                    ni, nj = i+di, j+dj
                    if 0<=ni<n and 0<=nj<m:
                        if mat[ni][nj] == 1:
                            ones.append((ni,nj))
                        elif candidate is None: # Found a 0 that borders exactly one 1
                            cnt = sum(mat[nii][njj] for nii, njj in [(ni-1,nj),(ni+1,nj),(ni,nj-1),(ni,nj+1)] if 0<=nii<n and 0<=njj<m)
                            if cnt == 1:
                                candidate = (ni, nj)
                if candidate is not None: break # Stop DFS
                stack.extend(ones)
            if candidate is not None:
                # Check if flipping candidate's neighbor disconnects the path
                for di, dj in dirs:
                    ni, nj = candidate[0]+di, candidate[1]+dj
                    if 0<=ni<n and 0<=nj<m and mat[ni][nj] == 0:
                        mat[ni][nj] = 1
                        visited2 = set([candidate])
                        stack = [p for p in visited if p != candidate]
                        while stack:
                            i, j = stack.pop()
                            visited2.add((i,j))
                            for di, dj in dirs:
                                ni, nj = i+di, j+dj
                                if 0<=ni<n and 0<=nj<m and mat[ni][nj] == 1 and (ni,nj) not in visited2:
                                    stack.append((ni,nj))
                        if isConnected(visited2): return True
                        mat[ni][nj] = 0 # Flip back
return False

The time complexity of this algorithm is O(n^3) in the worst case, since we explore all cells and for each cell we may do a DFS that visits all other cells. However, in practice this should be faster since in many cases we will stop DFS early after finding the candidate endpoint. Also, the isConnected function short-circuits as soon as it finds a path that intersects visited2, so it doesn't explore the entire grid.

The space complexity is O(n^2) because of the visited and visited2 sets, and the DFS stack.

1