Fewest Presses to Darken the Panel
HardMatrix
Problem
A control panel is an m × n grid of lamps; grid[r][c] is 1 if the lamp is on and 0 if it is off. Each lamp has a button. Pressing the button at (r, c) toggles that lamp and its up to four orthogonal neighbours (up, down, left, right).
Return the minimum number of presses needed to switch every lamp off, or -1 if it cannot be done.
Example 1
- Input:
- grid = [[1, 1, 0], [1, 0, 0], [0, 0, 0]]
- Output:
- 1
Pressing (0, 0) toggles (0, 0), (0, 1) and (1, 0), which are exactly the lit lamps.
Example 2
- Input:
- grid = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]
- Output:
- 1
Pressing the centre toggles the whole plus shape.
Example 3
- Input:
- grid = [[1, 0], [0, 0]]
- Output:
- 3
Pressing (0, 0), (0, 1) and (1, 0) toggles (0, 0) three times and every other lamp twice, so only (0, 0) changes. No one or two presses work.
Constraints
- 1 ≤ m ≤ 20
- 1 ≤ n ≤ 10
- grid[i][j] is 0 or 1
Hint
Show the first hint
Pressing a button twice cancels out, and the order of presses does not matter. So a solution is just a set of buttons.
Walkthrough
How to approach it
01Clarify before coding
- Do presses wrap around the edges? No, missing neighbours are simply skipped.
- Does the order of presses matter? No: toggles commute, and pressing a button twice undoes itself.
- What if it is impossible? Return -1; some patterns cannot be cleared.
02Brute force
Try every subset of the m · n buttons and keep the smallest subset that switches everything off.
Cost: O(2^(m·n) · m · n): already 2^25 subsets for a 5 × 5 panel, hopeless for 20 × 10.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.