2556. Disconnect Path in a Binary Matrix by at Most One Flip LeetCode Solution
In this guide, you will get 2556. Disconnect Path in a Binary Matrix by at Most One Flip LeetCode Solution with the best time and space complexity. The solution to Disconnect Path in a Binary Matrix by at Most One Flip problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Disconnect Path in a Binary Matrix by at Most One Flip
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.
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 <= 105
grid[i][j] is either 0 or 1.
grid[0][0] == grid[m – 1][n – 1] == 1
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(m + n)
2556. Disconnect Path in a Binary Matrix by at Most One Flip LeetCode Solution in C++
class Solution {
public:
bool isPossibleToCutPath(vector<vector<int>>& grid) {
if (!hasPath(grid, 0, 0))
return true;
// Reassign (0, 0) as 1.
grid[0][0] = 1;
return !hasPath(grid, 0, 0);
}
private:
// Returns true is there's a path from (0, 0) to (m - 1, n - 1).
// Also marks the visited path as 0 except (m - 1, n - 1).
bool hasPath(vector<vector<int>>& grid, int i, int j) {
if (i == grid.size() || j == grid[0].size())
return false;
if (i == grid.size() - 1 && j == grid[0].size() - 1)
return true;
if (grid[i][j] == 0)
return false;
grid[i][j] = 0;
// Go down first. Since we use OR logic, we'll only mark one path.
return hasPath(grid, i + 1, j) || hasPath(grid, i, j + 1);
}
}; /* code provided by PROGIEZ */
2556. Disconnect Path in a Binary Matrix by at Most One Flip LeetCode Solution in Java
class Solution {
public boolean isPossibleToCutPath(int[][] grid) {
if (!hasPath(grid, 0, 0))
return true;
// Reassign (0, 0) as 1.
grid[0][0] = 1;
return !hasPath(grid, 0, 0);
}
// Returns true is there's a path from (0, 0) to (m - 1, n - 1).
// Also marks the visited path as 0 except (m - 1, n - 1).
private boolean hasPath(int[][] grid, int i, int j) {
if (i == grid.length || j == grid[0].length)
return false;
if (i == grid.length - 1 && j == grid[0].length - 1)
return true;
if (grid[i][j] == 0)
return false;
grid[i][j] = 0;
// Go down first. Since we use OR logic, we'll only mark one path.
return hasPath(grid, i + 1, j) || hasPath(grid, i, j + 1);
}
} // code provided by PROGIEZ
2556. Disconnect Path in a Binary Matrix by at Most One Flip LeetCode Solution in Python
class Solution:
def isPossibleToCutPath(self, grid: list[list[int]]) -> bool:
# Returns True is there's a path from (0, 0) to (m - 1, n - 1).
# Also marks the visited path as 0 except (m - 1, n - 1).
def hasPath(i: int, j: int) -> bool:
if i == len(grid) or j == len(grid[0]):
return False
if i == len(grid) - 1 and j == len(grid[0]) - 1:
return True
if grid[i][j] == 0:
return False
grid[i][j] = 0
# Go down first. Since we use OR logic, we'll only mark one path.
return hasPath(i + 1, j) or hasPath(i, j + 1)
if not hasPath(0, 0):
return True
# Reassign (0, 0) as 1.
grid[0][0] = 1
return not hasPath(0, 0) # code by PROGIEZ
