Interview problem: Given a grid of 0s & 1s, remove min 1s such that no two 1s are adjacent

Given a grid ,with persons standing , some are empty spaces, we need to remove minimum number of person such that no two person are adjacent to each other (only horizontal and vertical are adjacent).

I found this problem in one of interview experience of Amazon at GFG. It would be great if anyone of you can help with the approach.


It would be great if any one of you guys can help me with the approach.

If we find some position (x,y) such that grid[x][y] = 1 and one of its neighbours is 1, we can remove the 1 on (x, y) because none of its neighbours are adjacent to each other ((x + 1, y), (x - 1, y), (x, y + 1) and (x, y - 1) are not adjacent so they all can be 1s but won’t be adjacent).
I would use this logic and do dfs to convert the grid.

Not sure if this is good enough…

1 Like

Dynamic programming approach:
Keep the values of the previous row in state and for each next row try all possible configurations such that no 2 adjacent set bits and prev_row_mask & curr_row_mask == 0.
The number of 1s removed in particular row will be set bits in (prev_row_mask ^ curr_row_mask).

This could be done in O(2^M * 2^N). But maybe a better solution exists