2123. Minimum Operations to Remove Adjacent Ones in Matrix


Problem Description

In this problem, we are provided with a binary matrix grid, where grid is comprised of 0s and 1s. The matrix is 0-indexed, meaning that both row and column indices start from 0. The problem requires us to perform operations on this matrix to achieve a specific condition known as "well-isolated." A binary matrix is said to be well-isolated if no 1 in the matrix is 4-directionally connected to another 1. In simpler terms, there should be no horizontally or vertically adjacent 1s in the entire matrix.

The operation we can perform is flipping any 1 in grid to become a 0. The problem poses the question of determining the minimum number of operations needed to make the grid well-isolated.

Intuition

To solve this problem, we need to determine pairs of adjacent 1s and then decide which 1 to flip in order to minimize the total number of operations. This leans towards a graph theoretical approach wherein we can model our 1s as vertices in a graph and the connections (adjacencies) as edges. The task then resembles a problem of finding a matching in the graph that covers the maximum number of vertices with the minimum number of edges – this is known as a maximum matching problem in a bipartite graph.

The solution uses adjacency lists (where each list contains indices of adjacent 1s), a matching array to keep track of the matchings, and a recursive function find() that tries to find augmenting paths and improve the existing matching. The indices are computed using the formula i * n + j to uniquely represent the cell at position (i, j) in a single integer, giving us a straightforward way to refer to specific cells in a linear fashion rather than as a 2D grid.

Here is how we arrive at the solution approach:

  1. Build a graph where each cell containing a 1 is considered a vertex.
  2. Connect vertices with edges if the corresponding 1s are horizontally or vertically adjacent.
  3. Use a bipartite matching algorithm to find the maximum number of matched edges – these represent pairs of 1s that can be flipped in a single operation.
  4. Since each matched edge represents two 1s that are adjacent, we flip one 1 in each matched pair.
  5. The minimum number of operations required is then equal to the number of matched edges.

So, we iteratively look for augmenting paths using the find() function, which follows the Ford-Fulkerson method in the bipartite matching context. Each time we find a new augmenting path, we increment our answer. At the end of the process, the ans variable holds the minimum number of operations required to make the grid well-isolated.

Solution Approach

The solution involves implementing a maximum matching algorithm on a bipartite graph. Here's a walk-through of the solution approach, incorporating algorithms, data structures, and design patterns:

  1. Initialization: First, a graph g is created using the defaultdict from Python's collections module, to hold the adjacency lists. An array match is initialized to -1 for all the cells in the grid, representing that initially, no 1 is matched to any other.

  2. Building the Graph:

    • Iterate through each cell (i, j) of the grid.
    • For each cell that contains a 1, compute its unique index x = i * n + j.
    • Check all four directions around cell (i, j) to find any adjacent 1s. For each adjacent 1, add the corresponding unique index to the adjacency list of x.
  3. Maximum Matching:

    • Iterate through each vertex in the graph g (which corresponds to each cell containing a 1).
    • Use a vis set to keep track of visited vertices during the search for an augmenting path to avoid revisiting them.
    • Call the recursive function find(i).
  4. Finding Augmenting Paths (find function):

    • For each adjacent vertex j of vertex i (corresponding to adjacent 1s):
      • Check if j was not visited already (to avoid cycles).
      • If match[j] is -1, it means j is unmatched and can be matched with i.
      • If match[j] is not -1, try to find an alternative path for the vertex matched with j (recursively calling find(match[j])).
      • If an augmenting path is found or j is unmatched, set match[j] to i and return 1.
  5. Counting Operations:

    • For each explored vertex i, the recursive call of find(i) will return 1 if a new match is found, incrementing the minimum number of operations (stored in ans).
  6. Result:

    • The variable ans now holds the total number of matches found, which is also the minimum number of operations needed to make the grid well-isolated. This is returned as the solution.

The main data structures used include a list for match that associates cells of the matrix which contain 1s with their matchings (or -1 if unmatched), and a defaultdict to create the adjacency list g. The set vis is used to facilitate the find function's tracking of visited vertices during each invocation. The designed approach leverages the concepts of bipartite matching and augmenting paths, employing a depth-first search-like algorithm to find matches.

The solution ensures that the operations are minimal since it leverages maximum matching—a fundamental concept ensuring the maximum number of connections with the minimum number of selections, which directly correlates to the minimal operational requirement of the given problem.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider the 3x3 binary matrix grid:

1grid = [
2    [1, 0, 0],
3    [0, 1, 1],
4    [0, 0, 1]
5]

Initialization

  • Create an empty graph g using a defaultdict for adjacency lists.
  • Initialize the match array to -1 for all cells, indicating no matches yet.

Building the Graph

  • We traverse the grid to build our graph. Here are the steps for each cell:
    • (0, 0): It's a 1. Its index is 0 * n + 0 = 0. No adjacent 1s.
    • (1, 1): It's a 1. Its index is 1 * n + 1 = 4. Adjacent to (1, 2) which has index 5, so we add 5 to g[4].
    • (1, 2): It's a 1. Its index is 1 * n + 2 = 5. Adjacent to (1, 1) and (2, 2), so we add 4 to g[5] and 8 to g[5].
    • (2, 2): It's a 1. Its index is 2 * n + 2 = 8. Adjacent to (1, 2), so add 5 to g[8].

Now, the adjacency list for g looks like this:

1g: {
2    4: [5],
3    5: [4, 8],
4    8: [5]
5}

Maximum Matching

  • We iterate over each vertex (4, 5, 8) in the graph g and attempt to find a match for each.
  • Initialize an empty set vis before each call to find().

Finding Augmenting Paths (find function)

  • For vertex 4, find(4) is called. Since g[4] = [5], we try to match it with 5.
    • 5 is not visited and match[5] is -1, so we set match[5] = 4 and find(4) returns 1.
  • Next, for vertex 5, find(5) finds adjacent vertices 4 and 8.
    • 4 is already matched with 5.
    • 8 is not visited and match[8] is -1, so we set match[8] = 5 and find(5) returns 1.
  • For vertex 8, find(8) returns 0 since its only adjacent vertex 5 is already matched with 8.

Counting Operations

  • For each match found, we increment our answer ans. In our case, find(4) and find(5) both returned 1, so ans is 2.

Result

  • We found two matches, which means we only need two operations to make the grid well-isolated. We can flip the 1s at the indices that correspond to any end of the matched pairs. In our matrix, we can flip 1 at (1, 1) and (1, 2), or (1, 2) and (2, 2).

The ans variable now holds the value 2, which is the minimum number of operations to make the grid well-isolated. This final result would then be returned by the algorithm.

Python Solution

1from collections import defaultdict
2
3class Solution:
4    def minimumOperations(self, grid: List[List[int]]) -> int:
5      
6        # Inner function to recursively find and match vertices in the matching graph
7        def find(i: int) -> int:
8            for neighbor in graph[i]:
9                if neighbor not in visited:
10                    visited.add(neighbor)
11                    if match[neighbor] == -1 or find(match[neighbor]):
12                        match[neighbor] = i
13                        return 1
14            return 0
15
16        # Initialize an adjacency list graph
17        graph = defaultdict(list)
18        rows, cols = len(grid), len(grid[0])
19      
20        # Construct the graph based on the grid: each on-cell is connected to its adjacent on-cells
21        for i, row in enumerate(grid):
22            for j, cell_value in enumerate(row):
23                if (i + j) % 2 == 1 and cell_value == 1:
24                    cell_key = i * cols + j
25                    # Connect to below cell
26                    if i < rows - 1 and grid[i + 1][j]:
27                        graph[cell_key].append(cell_key + cols)
28                    # Connect to above cell
29                    if i > 0 and grid[i - 1][j]:
30                        graph[cell_key].append(cell_key - cols)
31                    # Connect to right cell
32                    if j < cols - 1 and grid[i][j + 1]:
33                        graph[cell_key].append(cell_key + 1)
34                    # Connect to left cell
35                    if j > 0 and grid[i][j - 1]:
36                        graph[cell_key].append(cell_key - 1)
37
38        # Initialize the matching array where each entry -1 indicates no match yet
39        match = [-1] * (rows * cols)
40        answer = 0
41
42        # Attempt to find a match for each cell with an odd sum of indices that has a value of 1
43        for i in graph.keys():
44            # Set of visited cells to avoid revisiting
45            visited = set()
46            # If a match is found, increment the answer
47            answer += find(i)
48
49        # Return the minimum number of operations to remove an on-cell without turning off an entire row or column
50        return answer
51

Java Solution

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.List;
6import java.util.Map;
7import java.util.Set;
8
9class Solution {
10    private Map<Integer, List<Integer>> graph = new HashMap<>();
11    private Set<Integer> visited = new HashSet<>();
12    private int[] matchedNodes;
13
14    // Main method to compute the minimum number of operations.
15    public int minimumOperations(int[][] grid) {
16        int rows = grid.length, cols = grid[0].length;
17        // Build the graph where 1s are only considered when at an odd index sum.
18        for (int i = 0; i < rows; ++i) {
19            for (int j = 0; j < cols; ++j) {
20                // Check if the indexes sum up to an odd number and the value is 1.
21                if ((i + j) % 2 == 1 && grid[i][j] == 1) {
22                    int node = i * cols + j;
23                    // Connect the current node to its adjacent nodes if they also hold 1.
24                    addEdgeIfValid(node, i + 1, j, rows, cols, grid);
25                    addEdgeIfValid(node, i - 1, j, rows, cols, grid);
26                    addEdgeIfValid(node, i, j + 1, rows, cols, grid);
27                    addEdgeIfValid(node, i, j - 1, rows, cols, grid);
28                }
29            }
30        }
31        // Initialize matched nodes array with -1 (representing no matches).
32        matchedNodes = new int[rows * cols];
33        Arrays.fill(matchedNodes, -1);
34        int result = 0;
35        // Iterate through each node and try to find a match.
36        for (int node : graph.keySet()) {
37            result += findMatch(node);
38            visited.clear(); // Clear visited set for the next iteration.
39        }
40        return result;
41    }
42
43    // Helper method to establish an edge if the connecting node is valid.
44    private void addEdgeIfValid(int currentNode, int x, int y, int rows, int cols, int[][] grid) {
45        if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) {
46            int adjacentNode = x * cols + y;
47            graph.computeIfAbsent(currentNode, k -> new ArrayList<>()).add(adjacentNode);
48        }
49    }
50
51    // Attempt to find a match for node 'i'. Returns 1 if a match is found, 0 otherwise.
52    private int findMatch(int i) {
53        for (int j : graph.get(i)) {
54            // Try to match 'i' with unmatched node 'j' or recursively with the node matched with 'j'.
55            if (visited.add(j)) {
56                if (matchedNodes[j] == -1 || findMatch(matchedNodes[j]) == 1) {
57                    matchedNodes[j] = i; // Update the match.
58                    return 1; // Match found.
59                }
60            }
61        }
62        return 0; // No match found.
63    }
64}
65

C++ Solution

1class Solution {
2public:
3    int minimumOperations(vector<vector<int>>& grid) {
4        int rowCount = grid.size();
5        int colCount = grid[0].size();
6
7        // Matching represents the counterpart for every cell in the grid
8        vector<int> matching(rowCount * colCount, -1);
9
10        // Visited helps keep track of visited cells during a single iteration
11        unordered_set<int> visited;
12
13        // Graph stores the adjacency list for each cell
14        unordered_map<int, vector<int>> graph;
15
16        // Preparing the graph: iterate over the grid and linking neighbors
17        for (int i = 0; i < rowCount; ++i) {
18            for (int j = 0; j < colCount; ++j) {
19                // We are only interested in cells with odd sum of indices (i + j)
20                // and those that have a non-zero value.
21                if ((i + j) % 2 && grid[i][j]) {
22                    int currentIndex = i * colCount + j;
23
24                    // Add all possible adjacent cells if they have non-zero values
25                    if (i < rowCount - 1 && grid[i + 1][j]) {
26                        graph[currentIndex].push_back(currentIndex + colCount);
27                    }
28                    if (i > 0 && grid[i - 1][j]) {
29                        graph[currentIndex].push_back(currentIndex - colCount);
30                    }
31                    if (j < colCount - 1 && grid[i][j + 1]) {
32                        graph[currentIndex].push_back(currentIndex + 1);
33                    }
34                    if (j > 0 && grid[i][j - 1]) {
35                        graph[currentIndex].push_back(currentIndex - 1);
36                    }
37                }
38            }
39        }
40
41        // Answer to keep the count of the total number of operations.
42        int operationsCount = 0;
43
44        // Recursive function to find match for a cell.
45        function<int(int)> findMatch = [&](int current) -> int {
46            for (int& adjacent : graph[current]) {
47                // Continue only if the adjacent cell is not already visited
48                if (!visited.count(adjacent)) {
49                    visited.insert(adjacent);
50
51                    // If the counterpart cell is not yet matched or 
52                    // if the match can be relocated, then assign match
53                    if (matching[adjacent] == -1 || findMatch(matching[adjacent])) {
54                        matching[adjacent] = current;
55                        return 1;
56                    }
57                }
58            }
59            return 0;
60        };
61
62        // Iterate through each cell and try to find a match for it
63        for (auto& [cellIndex, _] : graph) {
64            operationsCount += findMatch(cellIndex);
65            // Clear the visited set for the next iteration
66            visited.clear();
67        }
68
69        // Return the total number of matched cells, which equals the minimum operations
70        return operationsCount;
71    }
72};
73

Typescript Solution

1function minimumOperations(grid: number[][]): number {
2    // Dimensions of the grid
3    const rows = grid.length;
4    const cols = grid[0].length;
5
6    // Initialize an array representing matching in augmented path
7    const match: number[] = Array(rows * cols).fill(-1);
8
9    // Set to keep track of visited nodes
10    const visited: Set<number> = new Set();
11
12    // Graph representation using a Map
13    const graph: Map<number, number[]> = new Map();
14
15    // Build the graph
16    for (let row = 0; row < rows; ++row) {
17        for (let col = 0; col < cols; ++col) {
18            // Check only odd cells with non-zero value
19            if ((row + col) % 2 && grid[row][col]) {
20                const index = row * cols + col; // Flatten the 2D grid to 1D
21                // Initialize adjacency list for the current cell
22                graph.set(index, []);
23
24                // Connect the current cell with adjacent cells with non-zero value
25                if (row < rows - 1 && grid[row + 1][col]) {
26                    graph.get(index)!.push(index + cols);
27                }
28                if (row > 0 && grid[row - 1][col]) {
29                    graph.get(index)!.push(index - cols);
30                }
31                if (col < cols - 1 && grid[row][col + 1]) {
32                    graph.get(index)!.push(index + 1);
33                }
34                if (col > 0 && grid[row][col - 1]) {
35                    graph.get(index)!.push(index - 1);
36                }
37            }
38        }
39    }
40
41    // Helper function to find augmenting paths
42    const find = (nodeIndex: number): number => {
43        for (const adjacent of graph.get(nodeIndex)!) {
44            if (!visited.has(adjacent)) {
45                visited.add(adjacent);
46                // If adjacent node is not part of matching or we found augmenting path
47                if (match[adjacent] === -1 || find(match[adjacent])) {
48                    match[adjacent] = nodeIndex; // Update the matching
49                    return 1;
50                }
51            }
52        }
53        return 0;
54    };
55
56    // Count of augmenting paths found
57    let numAugmentingPaths = 0;
58    // Loop through all nodes and try to find augmenting paths
59    for (const nodeIndex of graph.keys()) {
60        numAugmentingPaths += find(nodeIndex);
61        visited.clear(); // Clear the visited set for the next iteration
62    }
63
64    // Return the total count of augmenting paths found
65    return numAugmentingPaths;
66}
67

Time and Space Complexity

Time Complexity

The time complexity of the solution is determined by several factors:

  1. Building the graph: The graph g is constructed by iterating over each cell in the grid. There are m * n cells, where m is the number of rows and n is the number of columns in the grid. Therefore, constructing the graph has a time complexity of O(m * n).

  2. Finding matches: The function find attempts to find a match for each vertex. The worst-case scenario for this function is when it has to visit each of the m * n vertices once for each of the m * n vertices in g.keys(), leading to a complexity of O((m * n) * (m * n)), which can be simplified to O(m^2 * n^2).

Combining these two, the total time complexity of the minimumOperations function is dominated by the matching process and is O(m^2 * n^2).

Space Complexity

The space complexity is determined by the data structures used:

  1. Graph representation: The graph g and the match array collectively take up O(m * n) space.

  2. Visited set: The vis set can potentially hold all vertices in the worst case, thus taking O(m * n) space.

  3. The recursion stack: The find function is a recursive function, and in the worst-case scenario, the depth of the recursive stack can be the number of vertices in the graph, which is O(m * n).

Thus, the total space complexity is O(m * n) as it is the largest term and other terms are not dependent on different variables.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫