Minimum Operations to Remove Adjacent Ones in Matrix - Solution & Explanation
Problem Statement
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 either0or1.
Approach Overview
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.
Solution
We observe that if two 1s in the matrix are adjacent, they must belong to different groups. Therefore, we can treat all 1s in the matrix as vertices, and connect an edge between two adjacent 1s to construct a bipartite graph.
Then, the problem can be transformed into finding the minimum vertex cover of a bipartite graph, which means selecting the minimum number of vertices to cover all edges. Since the minimum vertex cover of a bipartite graph equals the maximum matching, we can use the Hungarian algorithm to find the maximum matching of the bipartite graph.
The core idea of the Hungarian algorithm is to continuously search for augmenting paths starting from unmatched vertices until no augmenting path exists, which yields the maximum matching.
The time complexity is O(m times n), where n and m are the number of 1s in the matrix and the number of edges, respectively.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
【每日一题】LeetCode 2123. Minimum Operations to Remove Adjacent Ones in Matrix • Huifeng Guan • 757 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Minimum Operations to Remove Adjacent Ones in Matrix easy or hard?
Minimum Operations to Remove Adjacent Ones in Matrix Python/Java solution
How to solve Minimum Operations to Remove Adjacent Ones in Matrix in O(n)?
What is the best approach for Minimum Operations to Remove Adjacent Ones in Matrix?
Is Minimum Operations to Remove Adjacent Ones in Matrix asked at Google/Amazon/Meta?
What data structure is used in Minimum Operations to Remove Adjacent Ones in Matrix?
What is the time complexity of Minimum Operations to Remove Adjacent Ones in Matrix?
Ready to solve this problem?
Practice Minimum Operations to Remove Adjacent Ones in Matrix with our built-in code editor and test cases.
Practice on FleetCode