We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Remove Adjacent Ones in Matrix

Number: 2259

Difficulty: Hard

Paid? Yes

Companies: Amazon

Problem Description

Given a 0-indexed binary matrix grid, you can flip any 1 in grid to 0 in one operation. A binary matrix is well-isolated if no 1 in the matrix is 4-directionally connected (i.e. horizontally or vertically) to another 1. Return the minimum number of operations required to make grid well-isolated.

Key Insights

  • The goal is to remove the minimum number of ones so that the remaining ones are not adjacent (up, down, left, right).
  • Instead of thinking about removals directly, we can view the problem as keeping the maximum number of ones that are isolated.
  • The selected ones must form an independent set in a graph where nodes represent ones and edges represent adjacent ones.
  • The grid can be bipartitioned (using a chessboard pattern) since any cell’s neighbors have the opposite color.
  • For a bipartite graph, the Maximum Independent Set size equals the total number of ones minus the Minimum Vertex Cover (by Kőnig’s theorem). And the minimum vertex cover size equals the maximum matching.
  • Hence, the minimum removals equal the size of the maximum matching in the bipartite graph induced by ones.

Space and Time Complexity

Time Complexity: O(V * E) in the worst-case using DFS-based augmenting path search; optimizations (like Hopcroft–Karp) can improve average-case performance. Space Complexity: O(V + E) for storing graph nodes and edges.

Solution

We use a bipartite matching approach. First, we assign cells with ones to two sets (based on (row+col) % 2). For each cell with a 1 in one set, we attempt to find an augmenting path to a neighboring 1 in the other set via DFS. The maximum number of matchings found corresponds to the minimum ones to remove (equal to the size of the maximum matching). We explicitly build edges for valid neighboring positions (up, down, left, right) and then run DFS-based matching to compute the maximum matching. Finally, the answer is the maximum matching count.

Code Solutions

# Python solution for Minimum Operations to Remove Adjacent Ones in Matrix

def minOperations(grid):
    # Dimensions of the grid
    m, n = len(grid), len(grid[0])
    
    # Helper function to check valid cell position
    def is_valid(x, y):
        return 0 <= x < m and 0 <= y < n
    
    # Directions for 4-connected neighbors: up, right, down, left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # Build graph from cells that are 1, only for cells in one bipartite set: (i+j) % 2 == 0
    graph = {}
    ones = 0  # Count total ones
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                ones += 1
                if (i + j) % 2 == 0:
                    # Use tuple (i, j) as node key
                    graph[(i, j)] = []
                    for dx, dy in directions:
                        ni, nj = i + dx, j + dy
                        if is_valid(ni, nj) and grid[ni][nj] == 1:
                            graph[(i, j)].append((ni, nj))
    
    # Dictionary to store matching from node in the other set to current node in left set.
    match = {}
    
    # DFS function to find an augmenting path from node 'u'
    def dfs(u, visited):
        for v in graph.get(u, []):
            if v in visited:
                continue
            visited.add(v)
            # If 'v' is not matched yet or we can find an alternative for previously matched node.
            if v not in match or dfs(match[v], visited):
                match[v] = u
                return True
        return False

    max_matching = 0
    # Try to find augmenting path from every node in the left side (bipartite color: (i+j)%2==0)
    for u in graph:
        if dfs(u, set()):
            max_matching += 1
    # The answer is the size of the maximum matching.
    return max_matching

# Example usage:
if __name__ == "__main__":
    grid1 = [[1,1,0],[0,1,1],[1,1,1]]
    print(minOperations(grid1))  # Expected output: 3
← Back to All Questions