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.

@hardik2001
@epsilon_573
@regular_coder
@sakshamceo
@shadow9236
@dpraveen

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