Minimum Operations to Remove Adjacent Ones in Matrix

This problem asks for the minimum number of operations to make a binary matrix "well-isolated," meaning no two '1's are adjacent horizontally or vertically. The solution leverages a maximum matching algorithm on a bipartite graph.

Approach

1. Bipartite Graph Construction: The matrix is transformed into a bipartite graph. Nodes represent '1's in the matrix. We divide the nodes into two sets based on the sum of their row and column indices:

   • Set A: Nodes where (row + column) is odd.
   • Set B: Nodes where (row + column) is even.

   An edge connects two nodes if they are adjacent (horizontally or vertically) in the matrix and both are '1's. This ensures that we only consider adjacent '1's.

2. Maximum Matching: We find the maximum matching in this bipartite graph. A matching is a set of edges where no two edges share a common node. The size of the maximum matching represents the maximum number of pairs of adjacent '1's that can be removed simultaneously.

3. Minimum Operations: The minimum number of operations is the total number of '1's in Set A minus the size of the maximum matching. This is because, in a maximum matching, we remove all the matched pairs. Then the remaining ones in set A need to be flipped to 0 to make the matrix well isolated.

Time Complexity Analysis

• Graph Construction: O(M*N), where M and N are the dimensions of the matrix. This is because we iterate through each cell once.
• Maximum Matching (Hopcroft-Karp Algorithm): O(Esqrt(V)), where E is the number of edges and V is the number of vertices (nodes) in the graph. In the worst case, E can be O(MN) and V can be O(MN). Therefore, the maximum matching step has a time complexity of O(MNsqrt(MN)). However, in practice, the number of edges is often smaller, leading to a faster runtime.

Therefore, the overall time complexity is dominated by the maximum matching step and is approximately O(MNsqrt(M*N)) in the worst case. The space complexity is also O(M*N) to store the graph and other data structures.

Code Explanation (Python)

from collections import defaultdict
 
class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        def find(i: int) -> int:
            for j in g[i]:
                if j not in vis:
                    vis.add(j)
                    if match[j] == -1 or find(match[j]):
                        match[j] = i
                        return 1
            return 0
 
        g = defaultdict(list)
        m, n = len(grid), len(grid[0])
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if (i + j) % 2 and v:  # Only consider nodes in Set A
                    x = i * n + j
                    if i < m - 1 and grid[i + 1][j]:
                        g[x].append(x + n)
                    if i and grid[i - 1][j]:
                        g[x].append(x - n)
                    if j < n - 1 and grid[i][j + 1]:
                        g[x].append(x + 1)
                    if j and grid[i][j - 1]:
                        g[x].append(x - 1)
 
        match = [-1] * (m * n)
        ans = 0
        for i in g.keys():
            vis = set()
            ans += find(i) # Find maximum matching using DFS
        return ans
 

The Python code implements a Depth-First Search (DFS) based approach to find the maximum matching. The find function recursively searches for augmenting paths in the bipartite graph. The main part of the code constructs the graph and then calls the find function for each node in Set A to find the maximum matching. The result is the number of nodes in Set A minus the size of the maximum matching. Other languages implement similar logic using different data structures and syntax.