Watch 2 video solutions for Minimum Operations to Remove Adjacent Ones in Matrix, a hard level problem involving Array, Graph, Matrix. This walkthrough by Huifeng Guan has 752 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed binary matrix grid. In one operation, you can flip any 1 in grid to be 0.
A binary matrix is well-isolated if there is no 1 in the matrix that is 4-directionally connected (i.e., horizontal and vertical) to another 1.
Return the minimum number of operations to make grid well-isolated.
Example 1:
Input: grid = [[1,1,0],[0,1,1],[1,1,1]] Output: 3 Explanation: Use 3 operations to change grid[0][1], grid[1][2], and grid[2][1] to 0. After, no more 1's are 4-directionally connected and grid is well-isolated.
Example 2:
Input: grid = [[0,0,0],[0,0,0],[0,0,0]] Output: 0 Explanation: There are no 1's in grid and it is well-isolated. No operations were done so return 0.
Example 3:
Input: grid = [[0,1],[1,0]] Output: 0 Explanation: None of the 1's are 4-directionally connected and grid is well-isolated. No operations were done so return 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is either 0 or 1.Problem Overview: You are given a binary matrix. Two cells containing 1 are considered adjacent if they share a side. The goal is to perform the minimum number of operations so that no two adjacent cells both contain 1.
The key observation: every pair of adjacent 1s forms a conflict. You must remove (or deactivate) some cells so that no conflicting pair remains. This turns the grid into a graph problem.
Approach 1: Brute Force Removal (Exponential Time, O(2^(m*n)) time, O(m*n) space)
Try every subset of cells to remove and check whether the remaining grid contains adjacent 1s. For each configuration, iterate through the matrix and verify adjacency in four directions. Track the minimum number of removals that produce a valid grid. This approach demonstrates the structure of the problem but becomes infeasible even for moderate grid sizes because the search space grows exponentially.
Approach 2: Bipartite Graph + Maximum Matching (Hungarian Algorithm) (O(V^3) time, O(V+E) space)
Treat each 1 cell as a node in a graph. Connect nodes if their cells are adjacent in the grid. Because the grid can be colored like a chessboard, the graph naturally splits into two partitions: cells where (row + col) % 2 == 0 and those where it equals 1. This forms a bipartite graph.
Each edge represents a conflict between two adjacent 1s. Removing the minimum number of cells to eliminate all conflicts is equivalent to finding the minimum vertex cover of this bipartite graph. By König’s theorem, the size of the minimum vertex cover equals the size of the maximum matching. You can compute this using the Hungarian algorithm or standard bipartite matching.
Build edges only from one partition to the other and run maximum matching. The number of matched pairs directly gives the minimum number of cells that must be removed to break all adjacencies.
This approach converts a matrix adjacency problem into a graph matching problem. The matching algorithm iteratively searches augmenting paths and updates pairings until no more improvements exist.
Recommended for interviews: Interviewers expect the bipartite graph modeling plus maximum matching solution. Recognizing the grid as a bipartite structure is the key insight. A brute-force explanation shows problem understanding, but implementing maximum matching using techniques from graph algorithms demonstrates strong algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Removal | O(2^(m*n)) | O(m*n) | Conceptual understanding or very small matrices |
| Bipartite Graph + Maximum Matching (Hungarian) | O(V^3) | O(V+E) | General optimal solution when modeling adjacency conflicts |
| DFS-based Bipartite Matching (Kuhn) | O(V*E) | O(V+E) | Practical implementation for medium grid sizes |