LeetCode 2123 - Minimum Operations to Remove Adjacent Ones in Matrix

The problem presents a binary matrix where each element is either 0 or 1. The goal is to transform this matrix into a well-isolated configuration, meaning that no 1 is 4-directionally connected to any other 1.

leetcodehardarraygraph-theorymatrix

LeetCode Problem 2123

Difficulty: 🔴 Hard
Topics: Array, Graph Theory, Matrix

Solution

Problem Understanding

The problem presents a binary matrix where each element is either 0 or 1. The goal is to transform this matrix into a well-isolated configuration, meaning that no 1 is 4-directionally connected to any other 1. A 4-directional connection refers to adjacency in the up, down, left, or right directions, excluding diagonals.

The input, grid, is an m x n matrix where 1 <= m, n <= 300, and each cell is either 0 or 1. The output is the minimum number of operations required to make the grid well-isolated. One operation consists of flipping a 1 into a 0.

From the constraints, we see that the matrix can be quite large, up to 90,000 cells, so a naive approach that examines all combinations of flips would be infeasible. The problem guarantees that the grid is valid and only contains 0s and 1s. Important edge cases include grids with all zeros (already well-isolated), grids with isolated 1s (no flips needed), and grids with large connected blocks of 1s where careful selection of which 1s to flip minimizes operations.

The challenge lies in efficiently identifying the minimum set of 1s to remove such that no two 1s remain adjacent, without redundantly flipping extra 1s.

Approaches

Brute Force

A naive solution would attempt to consider all subsets of 1s and check which subset results in a well-isolated grid. For each configuration, we would count the number of flips and track the minimum. While this approach guarantees correctness, it is computationally infeasible for matrices of size 300 x 300 because the number of 1s could be up to 90,000, resulting in 2^k combinations. This exponential growth is unacceptable for large inputs.

Optimal Approach

The key insight is to treat the problem as finding a maximum independent set in a graph where nodes are 1s and edges connect 4-directionally adjacent 1s. Removing a 1 corresponds to "deleting a node," and we want to minimize deletions, equivalent to maximizing the set of 1s we keep such that no two are adjacent.

Since the adjacency graph of 1s is bipartite (any 2D grid graph can be colored in a checkerboard pattern), we can leverage the König's theorem, which states that in a bipartite graph, the size of the maximum independent set equals the total nodes minus the size of the maximum matching. Thus, we can:

  1. Build a bipartite graph of 1s, colored as black and white based on a checkerboard pattern.
  2. Connect edges between adjacent 1s.
  3. Compute the maximum matching using a bipartite matching algorithm (like Hopcroft-Karp).
  4. The minimum number of flips is equal to the number of 1s minus the maximum independent set size, which is maximum matching in this bipartite setup.

This approach scales efficiently for the problem constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^k) O(k) Examines all subsets of 1s; impractical for large matrices
Optimal O(k * sqrt(k)) O(k) Uses bipartite graph matching via Hopcroft-Karp; scalable

Here, k is the total number of 1s in the grid.

Algorithm Walkthrough

  1. Iterate over the matrix to identify all positions of 1s and assign them a color (black or white) using a checkerboard pattern: (i + j) % 2.
  2. Build a bipartite graph: for each black node, connect it to all adjacent white nodes that are also 1s.
  3. Apply a maximum bipartite matching algorithm (Hopcroft-Karp) to find the largest set of edges where each black node matches with a white node.
  4. Compute the minimum number of flips as the total number of 1s minus the maximum independent set size, where maximum independent set size is equal to total_1s - matching_size.
  5. Return this minimum number of operations.

Why it works: The checkerboard coloring ensures the adjacency graph of 1s is bipartite, so every connected pair of 1s will be between a black and white node. By finding the maximum matching, we identify the minimal set of 1s that must be removed to eliminate all 4-directional connections. This guarantees correctness and minimality.

Python Solution

from typing import List
from collections import deque

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        total_ones = sum(row.count(1) for row in grid)
        
        # Mapping positions of 1s to indices
        pos_to_index = {}
        index = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    pos_to_index[(i,j)] = index
                    index += 1
        
        black_nodes = set()
        adj = [[] for _ in range(total_ones)]
        
        # Build bipartite graph
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    idx = pos_to_index[(i,j)]
                    if (i + j) % 2 == 0:
                        black_nodes.add(idx)
                        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                            ni, nj = i + dx, j + dy
                            if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                                adj[idx].append(pos_to_index[(ni,nj)])
        
        # Hopcroft-Karp for maximum bipartite matching
        match_to = [-1] * total_ones
        
        def bpm(u, visited):
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    if match_to[v] == -1 or bpm(match_to[v], visited):
                        match_to[v] = u
                        return True
            return False
        
        matching = 0
        for u in black_nodes:
            visited = [False] * total_ones
            if bpm(u, visited):
                matching += 1
        
        return matching

The implementation builds a bipartite graph where black nodes represent positions (i+j)%2==0 with value 1. Adjacency lists are constructed for each black node. The bpm function performs a depth-first search to find augmenting paths for the matching. The final matching count represents the minimum number of flips required.

Go Solution

func minimumOperations(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    posToIndex := make(map[[2]int]int)
    index := 0
    totalOnes := 0

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                posToIndex[[2]int{i,j}] = index
                index++
                totalOnes++
            }
        }
    }

    adj := make([][]int, totalOnes)
    blackNodes := []int{}
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                idx := posToIndex[[2]int{i,j}]
                if (i+j)%2 == 0 {
                    blackNodes = append(blackNodes, idx)
                    directions := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
                    for _, d := range directions {
                        ni, nj := i+d[0], j+d[1]
                        if ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1 {
                            adj[idx] = append(adj[idx], posToIndex[[2]int{ni,nj}])
                        }
                    }
                }
            }
        }
    }

    matchTo := make([]int, totalOnes)
    for i := range matchTo { matchTo[i] = -1 }

    var bpm func(int, []bool) bool
    bpm = func(u int, visited []bool) bool {
        for _, v := range adj[u] {
            if !visited[v] {
                visited[v] = true
                if matchTo[v] == -1 || bpm(matchTo[v], visited) {
                    matchTo[v] = u
                    return true
                }
            }
        }
        return false
    }

    matching := 0
    for _, u := range blackNodes {
        visited := make([]bool, totalOnes)
        if bpm(u, visited) {
            matching++
        }
    }

    return matching
}

In Go, slices and maps replace Python's lists and dictionaries. The DFS-based bipartite matching function is implemented as a closure to access matchTo and adj conveniently.

Worked Examples

Example 1

Input: [[1,1,0],[0,1,1],[1,1,1]]

Total ones = 7. Positions of