Minimum Operations to Remove Adjacent Ones in Matrix

Minimum Operations to Remove Adjacent Ones in Matrix - Problem

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.

Input & Output

Example 1 — Basic Adjacent 1s

$ Input: grid = [[1,1,0],[0,1,0],[0,0,1]]

› Output: 1

💡 Note: Remove the center 1 at position (1,1). This breaks both adjacencies: (0,0)-(0,1) and (0,1)-(1,1), making the matrix well-isolated with only isolated 1s remaining.

Example 2 — Multiple Groups

$ Input: grid = [[1,1],[1,1]]

› Output: 2

💡 Note: All four 1s are connected. We need to remove at least 2 of them to make remaining 1s non-adjacent. One optimal solution is to keep (0,0) and (1,1) which are diagonally positioned.

Example 3 — Already Well-Isolated

$ Input: grid = [[1,0,1],[0,0,0],[1,0,1]]

› Output: 0

💡 Note: All 1s are already isolated with no adjacent pairs. No operations needed.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 15
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with adjacent 1s that need separation

Find Minimum Removals

Identify which 1s to remove to eliminate all adjacencies

Well-Isolated Result

Final matrix with no adjacent 1s

Key Takeaway

🎯 Key Insight: Model as maximum independent set in bipartite graph to minimize removals

Asked in

G Google 15 f Meta 12 a Amazon 8

This problem requires finding the minimum number of 1s to remove so that no two 1s are adjacent. The key insight is to model this as a maximum independent set problem on a bipartite graph. Best approach uses bipartite matching with O(V³) time and O(V²) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Maximum Independent Set (Bipartite Graph)	O(V³)	O(V²)	Model as bipartite graph and find maximum independent set to minimize removals
Brute Force - Try All Combinations	O(2^k × m × n)	O(m × n)	Try all possible combinations of flipping 1s until matrix is well-isolated

Maximum Independent Set (Bipartite Graph) — Algorithm Steps

Step 1: Color matrix like chessboard (black/white based on i+j parity)
Step 2: Build bipartite graph connecting adjacent 1s of different colors
Step 3: Find maximum matching using Hungarian algorithm or flow
Step 4: Maximum independent set = total 1s - maximum matching

Visualization

Tap to expand

Step-by-Step Walkthrough

Chessboard Coloring

Color cells black/white based on (i+j) % 2

Build Bipartite Graph

Connect adjacent 1s of different colors

Maximum Matching

Find maximum matching to get independent set size

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int x, y;
} Point;

bool dfs(int u, int** graph, int* graphSizes, int* matchWhite, bool* visited, int whiteCount) {
    for (int i = 0; i < graphSizes[u]; i++) {
        int v = graph[u][i];
        if (visited[v]) continue;
        visited[v] = true;
        if (matchWhite[v] == -1 || dfs(matchWhite[v], graph, graphSizes, matchWhite, visited, whiteCount)) {
            matchWhite[v] = u;
            return true;
        }
    }
    return false;
}

int solution(int** grid, int m, int n) {
    Point blackOnes[1000], whiteOnes[1000];
    int blackCount = 0, whiteCount = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                if ((i + j) % 2 == 0) {
                    blackOnes[blackCount].x = i;
                    blackOnes[blackCount].y = j;
                    blackCount++;
                } else {
                    whiteOnes[whiteCount].x = i;
                    whiteOnes[whiteCount].y = j;
                    whiteCount++;
                }
            }
        }
    }
    
    int** graph = (int**)malloc(blackCount * sizeof(int*));
    int* graphSizes = (int*)calloc(blackCount, sizeof(int));
    
    for (int i = 0; i < blackCount; i++) {
        graph[i] = (int*)malloc(whiteCount * sizeof(int));
    }
    
    int directions[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    for (int i = 0; i < blackCount; i++) {
        int r1 = blackOnes[i].x, c1 = blackOnes[i].y;
        for (int d = 0; d < 4; d++) {
            int nr = r1 + directions[d][0], nc = c1 + directions[d][1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                for (int j = 0; j < whiteCount; j++) {
                    if (whiteOnes[j].x == nr && whiteOnes[j].y == nc) {
                        graph[i][graphSizes[i]++] = j;
                        break;
                    }
                }
            }
        }
    }
    
    int* matchWhite = (int*)malloc(whiteCount * sizeof(int));
    for (int i = 0; i < whiteCount; i++) {
        matchWhite[i] = -1;
    }
    
    int matching = 0;
    for (int i = 0; i < blackCount; i++) {
        bool* visited = (bool*)calloc(whiteCount, sizeof(bool));
        if (dfs(i, graph, graphSizes, matchWhite, visited, whiteCount)) {
            matching++;
        }
        free(visited);
    }
    
    for (int i = 0; i < blackCount; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSizes);
    free(matchWhite);
    
    return matching;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int grid[10][10];
    int m = 0, n = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    grid[m][n++] = *ptr - '0';
                }
                ptr++;
            }
            m++;
        }
        ptr++;
    }
    
    int** gridPtr = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        gridPtr[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            gridPtr[i][j] = grid[i][j];
        }
    }
    
    printf("%d\n", solution(gridPtr, m, n));
    
    for (int i = 0; i < m; i++) {
        free(gridPtr[i]);
    }
    free(gridPtr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V³)

Hungarian algorithm or max flow for bipartite matching with V vertices

✓ Linear Growth

Space Complexity

O(V²)

Adjacency matrix for bipartite graph representation

✓ Linear Space

3.2K Views

Medium Frequency

~35 min Avg. Time

89 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Maximum Independent Set (Bipartite Graph) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler