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

Problem Description

Explanation

To solve this problem, we can use a breadth-first search (BFS) approach. We start by flipping each cell one by one and perform a BFS to check if there is a path from (0, 0) to (m-1, n-1) in the modified grid. If at any point we find that there is no path, we can return true as it means that by flipping that cell, we disconnected the matrix. If we reach the end and there is still a path, we return false.

Algorithm:

Create a helper function hasPath that performs a BFS to check if there is a path from (0, 0) to (m-1, n-1).
Iterate through each cell of the grid and flip it.
For each flipped cell, call the hasPath function to check if there is a path.
If at any point hasPath returns false, return true.
If no cell can disconnect the matrix, return false.

Time Complexity: O(mn) where m and n are the dimensions of the grid. Space Complexity: O(mn) for the queue used in BFS.

Solutions

class Solution {
    public boolean hasPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int row = curr[0];
            int col = curr[1];
            
            if (row == m - 1 && col == n - 1) {
                return true;
            }
            
            visited[row][col] = true;
            
            int[][] dirs = {{1, 0}, {0, 1}};
            for (int[] dir : dirs) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol] && grid[newRow][newCol] == 1) {
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
        
        return false;
    }
    
    public boolean canDisconnect(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0 || i == m - 1 && j == n - 1) {
                    continue;
                }
                
                int original = grid[i][j];
                grid[i][j] = 1 - original;
                
                if (!hasPath(grid)) {
                    return true;
                }
                
                grid[i][j] = original;
            }
        }
        
        return false;
    }
}

Problem Description

Explanation

Solutions

Related LeetCode Problems