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

Master LeetCode problem 2556 (Disconnect Path in a Binary Matrix by at Most One Flip), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2556. Disconnect Path in a Binary Matrix by at Most One Flip

Medium

Array Dynamic Programming Depth-First Search Breadth-First Search Matrix

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2556 (Disconnect Path in a Binary Matrix by at Most One Flip)?

This page provides optimized solutions for LeetCode problem 2556 (Disconnect Path in a Binary Matrix by at Most One Flip) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2556 (Disconnect Path in a Binary Matrix by at Most One Flip)?

The time complexity for LeetCode 2556 (Disconnect Path in a Binary Matrix by at Most One Flip) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2556 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2556 in Java, C++, or Python.

Back to LeetCode Solutions