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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Disconnect Path in a Binary Matrix by at Most One Flip

Difficulty: Medium

Problem Description

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. The matrix is disconnected if there is no path from (0, 0) to (m - 1, n - 1). You can flip the value of at most one cell. You cannot flip the cells (0, 0) and (m - 1, n - 1). Return true if it is possible to make the matrix disconnect or false otherwise.

Key Insights

  • The path from (0, 0) to (m - 1, n - 1) can be blocked by flipping a strategically chosen cell from 1 to 0.
  • The primary movement is downwards or to the right, which means we need to consider the connectivity of the path based on these movements.
  • If there is already a path from (0, 0) to (m - 1, n - 1) without any flips, we must evaluate if flipping any neighboring cell of the current path will disconnect it.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve the problem, we can use a breadth-first search (BFS) or depth-first search (DFS) algorithm. The idea is to first find if there is a valid path from (0, 0) to (m - 1, n - 1) without any flips. If such a path exists, we then check the neighboring cells of this path to see if flipping any of them to 0 will disconnect the path. We can represent the grid with a queue (for BFS) or a stack (for DFS) to explore all possible paths and check connectivity.

Code Solutions

from collections import deque

def can_disconnect(grid):
    m, n = len(grid), len(grid[0])
    
    # Function to check if there's a path from (0, 0) to (m-1, n-1)
    def bfs_check_path():
        if grid[0][0] == 0 or grid[m-1][n-1] == 0:
            return False
        queue = deque([(0, 0)])
        visited = set((0, 0))
        
        while queue:
            x, y = queue.popleft()
            if (x, y) == (m-1, n-1):
                return True
            
            for dx, dy in [(1, 0), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))
        
        return False

    if not bfs_check_path():
        return True  # Already disconnected

    # Check neighboring cells of the path
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                grid[i][j] = 0  # Flip cell
                if not bfs_check_path():
                    return True  # Disconnected
                grid[i][j] = 1  # Restore cell

    return False
← Back to All Questions