We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Disconnect Path in a Binary Matrix by at Most One Flip

Number: 2641

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an m x n binary matrix grid, you can only move either down or right from a cell (row, col) and only if the destination cell has value 1. The grid is considered disconnected if there is no valid 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 (change a 1 to 0 or vice versa), except for the start and the end cells. Return true if it is possible to disconnect the grid by at most one flip; otherwise, return false.

Key Insights

  • First, check if a valid path exists; if the matrix is already disconnected, return true.
  • If a path exists, compute one valid path from start to finish using DFS/BFS.
  • The idea is to try flipping a cell on this path (except the endpoints) and then re-check connectivity.
  • Usually, flipping the second cell in the found path is a promising candidate because if multiple alternative paths existed, that cell would not be critical.
  • After “removing” (or flipping) that candidate cell (simulate by marking it as 0), re-run the search to see if the path is broken.

Space and Time Complexity

Time Complexity: O(mn) – We traverse the grid several times (once to get the initial path and once more to check connectivity after a flip). Space Complexity: O(mn) – The recursion/queue storage may hold up to all cells in worst case.

Solution

We start by searching for an initial valid path from (0, 0) to (m - 1, n - 1) using DFS (or BFS). If no path exists initially, the grid is already disconnected and we return true.

If a path is found, we choose a candidate cell (typically the second cell in the path, ensuring it is not the start or end) as the cell to flip. The intuition is that if this candidate cell is “critical” (i.e. every valid path must pass through it), flipping it will disconnect the grid. We then simulate flipping the candidate cell by marking it as 0 and run another DFS/BFS from (0, 0) to (m - 1, n - 1). If no new path exists, then flipping that cell is sufficient to disconnect the grid and we return true. Otherwise, if an alternative path exists, it means no single flip can disconnect the grid and we return false.

Important details:

  • Always ensure that the endpoints (start and finish) are not flipped.
  • The search is limited to moves down and right, so the candidate cell’s removal might cut off all possible paths if it is unique to them.
  • Corner cases such as very short paths (e.g. grid of size 1 x n or m x 1) should be handled carefully.

Code Solutions

# Python solution for disconnecting the path in a binary matrix.

from collections import deque

def is_path(grid):
    m, n = len(grid), len(grid[0])
    # Use BFS to determine if a path exists from (0, 0) to (m-1, n-1)
    queue = deque([(0, 0)])
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True
    while queue:
        x, y = queue.popleft()
        # reached destination
        if x == m - 1 and y == n - 1:
            return True
        # Only moves allowed: right and down.
        for dx, dy in [(0, 1), (1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))
    return False

def find_path(grid):
    # DFS to record one path from (0,0) to (m-1, n-1)
    m, n = len(grid), len(grid[0])
    path = []
    visited = [[False] * n for _ in range(m)]
    found = False

    def dfs(x, y):
        nonlocal found
        # add current cell to path
        path.append((x, y))
        if x == m - 1 and y == n - 1:
            found = True
            return
        # mark visited
        visited[x][y] = True
        for dx, dy in [(0, 1), (1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and not visited[nx][ny]:
                dfs(nx, ny)
                if found:
                    return
        # backtrack if no valid path found from here
        path.pop()
    
    dfs(0, 0)
    return path if found else None

def can_disconnect(grid):
    m, n = len(grid), len(grid[0])
    # If there's no path initially, we are already disconnected.
    if not is_path(grid):
        return True

    # Get one valid path from start to finish.
    path = find_path(grid)
    # If path doesn't exist (shouldn't happen as is_path returned True), return False
    if not path:
        return False

    # If the path is too short (meaning only endpoints) then no cell to flip.
    if len(path) <= 2:
        return False
    
    # Choose candidate cell to flip: typically choose the second cell in the path.
    x_flip, y_flip = path[1]
    
    # Temporarily flip the chosen cell.
    original_value = grid[x_flip][y_flip]
    grid[x_flip][y_flip] = 0
    
    # Check if there is still a path.
    disconnected = not is_path(grid)
    
    # Restore the grid (if needed in further calls or debugging).
    grid[x_flip][y_flip] = original_value
    
    return disconnected

# Example usage:
grid1 = [[1,1,1],[1,0,0],[1,1,1]]
print(can_disconnect(grid1))  # Expected output: True

grid2 = [[1,1,1],[1,0,1],[1,1,1]]
print(can_disconnect(grid2))  # Expected output: False
← Back to All Questions