Jobs

Interviews

Discussions

Disconnect Path in a Binary Matrix by at Most One Flip

Medium

Asked by:

22 views

Topics:

Graphs

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 (possibly none) 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.

Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.

Example 1:

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.

Example 2:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: false
Explanation: It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).

Constraints:

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

Try coding it in LeetCode

Disconnect Path in a Binary Matrix by at Most One Flip

Medium

Asked by:

22 views

Topics:

Graphs

You can flip the value of at most one (possibly none) 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.

Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.

Example 1:

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.

Example 2:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: false
Explanation: It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the binary matrix (number of rows and columns), and what are the constraints on these dimensions (e.g., minimum or maximum values)?
Is a path considered 'disconnected' if there are no paths from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1), or are there specific requirements for what constitutes a 'disconnected' path?
By 'flip', do you mean changing a 0 to a 1, or a 1 to a 0, or both? Is it guaranteed that the cells only contain 0s and 1s?
If there is no path from the top-left cell to the bottom-right cell initially, should I return true without flipping any cells?
Is it guaranteed that the top-left and bottom-right cells will always be '1' initially, or could they be '0' and require a flip to start/complete a path?

Brute Force Solution

Approach

The goal is to see if we can block all paths from the top-left corner to the bottom-right corner of a grid by changing at most one cell's value. A brute force strategy systematically tries every single possible cell flip and then checks if doing so disconnects the path.

Here's how the algorithm would work step-by-step:

First, check if there is already no path from the start to the end of the original grid. If there isn't, we don't need to flip anything, and we're done.
If there *is* a path, then we'll consider each cell in the grid one by one.
For each cell, we'll temporarily flip its value (change a 1 to a 0, or a 0 to a 1).
After flipping the value of that cell, we will check if there is still a path from the start to the end of the grid.
If there is no path from the start to the end after flipping that cell, then we have found a solution, so we can stop.
If we go through every cell, flipping it, and checking for a path, and we never find a cell that disconnects the path, then it is impossible to disconnect the path with at most one flip.

Code Implementation

def can_disconnect_path_brute_force(grid):
    rows = len(grid)
    cols = len(grid[0])

    def has_path(current_grid):
        visited = set()

        def dfs(row, col):
            if row < 0 or row >= rows or col < 0 or col >= cols or \
               (row, col) in visited or current_grid[row][col] == 0:
                return False

            if row == rows - 1 and col == cols - 1:
                return True

            visited.add((row, col))

            return (dfs(row + 1, col) or
                    dfs(row - 1, col) or
                    dfs(row, col + 1) or
                    dfs(row, col - 1))

        return dfs(0, 0)

    # If no path exists to begin with, return True
    if not has_path(grid):
        return True

    for row in range(rows):
        for col in range(cols):
            original_value = grid[row][col]
            
            # Temporarily flip the cell value
            grid[row][col] = 1 - original_value

            # Check if a path still exists
            if not has_path(grid):
                return True

            # Restore the original value
            grid[row][col] = original_value

    # No single flip disconnects the path
    return False

Big(O) Analysis

Time Complexity

O(n*m*(n+m)) – The outer loop iterates through each cell in the n x m grid, which takes O(n*m) time. Inside the loop, we temporarily flip the cell's value. Then, we check if there's a path from the top-left to the bottom-right corner. Path checking can be done using Depth First Search (DFS) or Breadth First Search (BFS). In the worst case, DFS/BFS might visit every cell in the grid (n*m cells) and for each cell explores up to four neighbors, meaning DFS/BFS takes O(n+m) where n and m are number of rows and columns. Therefore, the overall time complexity becomes O(n*m) * O(n+m) = O(n*m*(n+m)).

Space Complexity

O(M*N) – The space complexity is determined by the path checking algorithm which is likely a Depth First Search (DFS) or Breadth First Search (BFS). These algorithms require a 'visited' matrix or set to keep track of visited cells to prevent cycles. In the worst case, the entire matrix might be part of a path, requiring a boolean matrix of the same size as the input grid (M rows and N columns) to mark visited cells. Therefore, the auxiliary space used is proportional to M*N, where M is the number of rows and N is the number of columns in the grid.

Optimal Solution

Approach

The goal is to determine if flipping at most one zero to a one can disconnect a path from the top-left to the bottom-right in a matrix. The clever idea is to use Depth-First Search (DFS) to find a path and then intelligently check if removing parts of that path disconnects the matrix or not.

Here's how the algorithm would work step-by-step:

First, try to find a path from the top-left corner to the bottom-right corner using the ones in the matrix. Think of it like finding a road through the matrix.
If no path exists to begin with, then we already know that we can return true because the matrix is already disconnected.
If a path exists, we need to see if flipping one zero to a one will create a disconnection. Instead of bruteforcing all zero flips, we are going to remove one from our path, and see if the matrix is still connected.
Now, remove the first 'one' from your previously found path, and see if another path exists from the top-left to the bottom-right.
If removing this 'one' disconnects the matrix, then we have found our answer and can return true. If not, put the 'one' back.
Repeat this process for each 'one' in the path you found earlier.
If removing any of the 'ones' disconnects the matrix, you can return true immediately. If you make it through all ones in the path and none disconnect the matrix, that means you cannot disconnect the matrix by flipping only one zero to a one. So return false.

Code Implementation

def can_disconnect(matrix):
    rows = len(matrix)
    cols = len(matrix[0])

    def depth_first_search(row, col, visited, current_matrix):
        if row < 0 or row >= rows or col < 0 or col >= cols or current_matrix[row][col] == 0 or (row, col) in visited:
            return False
        if row == rows - 1 and col == cols - 1:
            return True

        visited.add((row, col))

        if depth_first_search(row + 1, col, visited, current_matrix):
            return True
        if depth_first_search(row - 1, col, visited, current_matrix):
            return True
        if depth_first_search(row, col + 1, visited, current_matrix):
            return True
        if depth_first_search(row, col - 1, visited, current_matrix):
            return True

        return False

    # Check if the matrix is already disconnected.
    if not depth_first_search(0, 0, set(), matrix):
        return True

    # Find a path from top-left to bottom-right.
    path = []
    def find_path(row, col, current_path, visited):
        if row < 0 or row >= rows or col < 0 or col >= cols or matrix[row][col] == 0 or (row, col) in visited:
            return False
        
        current_path.append((row, col))
        visited.add((row, col))

        if row == rows - 1 and col == cols - 1:
            return True

        if find_path(row + 1, col, current_path, visited):
            return True
        if find_path(row - 1, col, current_path, visited):
            return True
        if find_path(row, col + 1, current_path, visited):
            return True
        if find_path(row, col - 1, current_path, visited):
            return True

        current_path.pop()
        return False

    find_path(0, 0, path, set())

    # Iterate through the path and check if removing a 'one' disconnects the matrix.
    for row, col in path:
        # Temporarily remove the 'one' from the matrix.
        temp_matrix = [row[:] for row in matrix]
        temp_matrix[row][col] = 0

        # Check if the matrix is disconnected after removing the 'one'.
        if not depth_first_search(0, 0, set(), temp_matrix):
            # This means we can disconnect the matrix by flipping at most one zero.
            return True

    return False

Big(O) Analysis

Time Complexity

O(n*m) – The initial Depth-First Search (DFS) to find a path from the top-left to bottom-right cell in the n x m matrix takes O(n*m) in the worst case, where n is the number of rows and m is the number of columns. If a path is found, the algorithm iterates through each cell in that path. For each cell in the path, another DFS is performed to check if removing that cell disconnects the matrix. This second DFS also takes O(n*m) in the worst case. Since the length of the path is at most n*m (the entire matrix), and we perform a DFS of O(n*m) complexity for each element in the path, the overall time complexity becomes O(n*m * n*m) for path removal and disconnection tests, plus O(n*m) for the initial path find. Therefore the solution runtime is dominated by O(n*m * n*m), or O((n*m)^2), which however can be optimized to O(n*m) if we avoid recomputing a path every time.

Space Complexity

O(N) – The algorithm uses Depth-First Search (DFS) which relies on a recursion stack. In the worst-case scenario, the path from the top-left to the bottom-right corner could traverse most of the matrix, leading to a recursion depth proportional to the number of cells in the matrix, which we can denote as N. Additionally, to reconstruct a path, a list is used to store the cells along the path from top-left to bottom-right, which at most, could contain all cells in the matrix. Thus, the auxiliary space is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty matrix	Return True immediately, as there's no path to disconnect.
1x1 matrix with value 1	Return False, as there is no path and no flip can create one.
1x1 matrix with value 0	Return True, as the matrix is already disconnected.
1xN or Nx1 matrix containing only 1s	Return False, as flipping any single 1 will not disconnect the path.
Matrix with all 0s	Return True, already disconnected.
Matrix where all paths from (0,0) to (m-1, n-1) pass through a single cell.	Check if flipping that cell disconnects the path, otherwise return False.
Large matrix that could lead to stack overflow with DFS/recursion	Use iterative DFS or BFS to avoid stack overflow errors.
Matrix with no path from (0,0) to (m-1, n-1) initially.	Return True as it is already disconnected.

Null or empty matrix

How to Handle:

Return True immediately, as there's no path to disconnect.

1x1 matrix with value 1

How to Handle:

Return False, as there is no path and no flip can create one.

1x1 matrix with value 0

How to Handle:

Return True, as the matrix is already disconnected.

1xN or Nx1 matrix containing only 1s

How to Handle:

Return False, as flipping any single 1 will not disconnect the path.

Matrix with all 0s

How to Handle:

Return True, already disconnected.

Matrix where all paths from (0,0) to (m-1, n-1) pass through a single cell.

How to Handle:

Check if flipping that cell disconnects the path, otherwise return False.

Large matrix that could lead to stack overflow with DFS/recursion

How to Handle:

Use iterative DFS or BFS to avoid stack overflow errors.

Matrix with no path from (0,0) to (m-1, n-1) initially.

How to Handle:

Return True as it is already disconnected.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the binary matrix (number of rows and columns), and what are the constraints on these dimensions (e.g., minimum or maximum values)?
Is a path considered 'disconnected' if there are no paths from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1), or are there specific requirements for what constitutes a 'disconnected' path?
By 'flip', do you mean changing a 0 to a 1, or a 1 to a 0, or both? Is it guaranteed that the cells only contain 0s and 1s?
If there is no path from the top-left cell to the bottom-right cell initially, should I return true without flipping any cells?
Is it guaranteed that the top-left and bottom-right cells will always be '1' initially, or could they be '0' and require a flip to start/complete a path?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if there is already no path from the start to the end of the original grid. If there isn't, we don't need to flip anything, and we're done.
If there *is* a path, then we'll consider each cell in the grid one by one.
For each cell, we'll temporarily flip its value (change a 1 to a 0, or a 0 to a 1).
After flipping the value of that cell, we will check if there is still a path from the start to the end of the grid.
If there is no path from the start to the end after flipping that cell, then we have found a solution, so we can stop.
If we go through every cell, flipping it, and checking for a path, and we never find a cell that disconnects the path, then it is impossible to disconnect the path with at most one flip.

Code Implementation

def can_disconnect_path_brute_force(grid):
    rows = len(grid)
    cols = len(grid[0])

    def has_path(current_grid):
        visited = set()

        def dfs(row, col):
            if row < 0 or row >= rows or col < 0 or col >= cols or \
               (row, col) in visited or current_grid[row][col] == 0:
                return False

            if row == rows - 1 and col == cols - 1:
                return True

            visited.add((row, col))

            return (dfs(row + 1, col) or
                    dfs(row - 1, col) or
                    dfs(row, col + 1) or
                    dfs(row, col - 1))

        return dfs(0, 0)

    # If no path exists to begin with, return True
    if not has_path(grid):
        return True

    for row in range(rows):
        for col in range(cols):
            original_value = grid[row][col]
            
            # Temporarily flip the cell value
            grid[row][col] = 1 - original_value

            # Check if a path still exists
            if not has_path(grid):
                return True

            # Restore the original value
            grid[row][col] = original_value

    # No single flip disconnects the path
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, try to find a path from the top-left corner to the bottom-right corner using the ones in the matrix. Think of it like finding a road through the matrix.
If no path exists to begin with, then we already know that we can return true because the matrix is already disconnected.
If a path exists, we need to see if flipping one zero to a one will create a disconnection. Instead of bruteforcing all zero flips, we are going to remove one from our path, and see if the matrix is still connected.
Now, remove the first 'one' from your previously found path, and see if another path exists from the top-left to the bottom-right.
If removing this 'one' disconnects the matrix, then we have found our answer and can return true. If not, put the 'one' back.
Repeat this process for each 'one' in the path you found earlier.
If removing any of the 'ones' disconnects the matrix, you can return true immediately. If you make it through all ones in the path and none disconnect the matrix, that means you cannot disconnect the matrix by flipping only one zero to a one. So return false.

Code Implementation

def can_disconnect(matrix):
    rows = len(matrix)
    cols = len(matrix[0])

    def depth_first_search(row, col, visited, current_matrix):
        if row < 0 or row >= rows or col < 0 or col >= cols or current_matrix[row][col] == 0 or (row, col) in visited:
            return False
        if row == rows - 1 and col == cols - 1:
            return True

        visited.add((row, col))

        if depth_first_search(row + 1, col, visited, current_matrix):
            return True
        if depth_first_search(row - 1, col, visited, current_matrix):
            return True
        if depth_first_search(row, col + 1, visited, current_matrix):
            return True
        if depth_first_search(row, col - 1, visited, current_matrix):
            return True

        return False

    # Check if the matrix is already disconnected.
    if not depth_first_search(0, 0, set(), matrix):
        return True

    # Find a path from top-left to bottom-right.
    path = []
    def find_path(row, col, current_path, visited):
        if row < 0 or row >= rows or col < 0 or col >= cols or matrix[row][col] == 0 or (row, col) in visited:
            return False
        
        current_path.append((row, col))
        visited.add((row, col))

        if row == rows - 1 and col == cols - 1:
            return True

        if find_path(row + 1, col, current_path, visited):
            return True
        if find_path(row - 1, col, current_path, visited):
            return True
        if find_path(row, col + 1, current_path, visited):
            return True
        if find_path(row, col - 1, current_path, visited):
            return True

        current_path.pop()
        return False

    find_path(0, 0, path, set())

    # Iterate through the path and check if removing a 'one' disconnects the matrix.
    for row, col in path:
        # Temporarily remove the 'one' from the matrix.
        temp_matrix = [row[:] for row in matrix]
        temp_matrix[row][col] = 0

        # Check if the matrix is disconnected after removing the 'one'.
        if not depth_first_search(0, 0, set(), temp_matrix):
            # This means we can disconnect the matrix by flipping at most one zero.
            return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return True immediately, as there's no path to disconnect.
1x1 matrix with value 1	Return False, as there is no path and no flip can create one.
1x1 matrix with value 0	Return True, as the matrix is already disconnected.
1xN or Nx1 matrix containing only 1s	Return False, as flipping any single 1 will not disconnect the path.
Matrix with all 0s	Return True, already disconnected.
Matrix where all paths from (0,0) to (m-1, n-1) pass through a single cell.	Check if flipping that cell disconnects the path, otherwise return False.
Large matrix that could lead to stack overflow with DFS/recursion	Use iterative DFS or BFS to avoid stack overflow errors.
Matrix with no path from (0,0) to (m-1, n-1) initially.	Return True as it is already disconnected.

Null or empty matrix

How to Handle:

Return True immediately, as there's no path to disconnect.

1x1 matrix with value 1

How to Handle:

Return False, as there is no path and no flip can create one.

1x1 matrix with value 0

How to Handle:

Return True, as the matrix is already disconnected.

1xN or Nx1 matrix containing only 1s

How to Handle:

Return False, as flipping any single 1 will not disconnect the path.

Matrix with all 0s

How to Handle:

Return True, already disconnected.

Matrix where all paths from (0,0) to (m-1, n-1) pass through a single cell.

How to Handle:

Check if flipping that cell disconnects the path, otherwise return False.

Large matrix that could lead to stack overflow with DFS/recursion

How to Handle:

Use iterative DFS or BFS to avoid stack overflow errors.

Matrix with no path from (0,0) to (m-1, n-1) initially.

How to Handle:

Return True as it is already disconnected.