Google | Phone Screen | Lights Out Puzzle
24342

Given a binary 2D grid (each element can either be a 1 or a 0). You have the ability to choose any element and flip its value. The only condition is that when you choose to flip any element at index (r, c), the 4 neighbors of that element also get flipped. Find the minimum number of flips that you need to do in order to set all the elements in the matrix equal to 0. If it's not possible, return -1.

Example 1:

Input:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

Output: 0

Example 2:

Input:
[[0, 1, 0],
 [1, 1, 1],
 [0, 1, 0]]

Output: 1
Explanation: Flip (1, 1) to make the whole matrix consisting of only 0s.

Example 3:

Input:
[[0, 1, 0],
 [1, 1, 0],
 [0, 1, 1]]

Output: 4
Explanation:
1. Flip (0, 0)
[[1, 0, 0],
 [0, 1, 0],
 [0, 1, 1]]

2. Flip (0, 1)
[[0, 1, 1],
 [0, 0, 0],
 [0, 1, 1]]

3. Flip (0, 2)
[[0, 0, 0],
 [0, 0, 1],
 [0, 1, 1]]

4. Flip (2, 2)
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Comments (53)