Update a Neuron Grid
Company: Scale AI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an `m x n` integer matrix `neurons`.
- A cell is a **firing** neuron if its value is `0`.
- A cell is a **non-firing** neuron if its value is greater than `0`.
For each cell, count the number of firing neighbors among its 8 surrounding cells (horizontal, vertical, and diagonal). All updates must be applied **simultaneously** based on the original state of the matrix.
Update the matrix using these rules:
1. If a cell is firing (`0`) and **exactly 3** of its neighbors are firing, its new value becomes `6`.
2. If a cell is non-firing and it has **0 or 1** firing neighbors, decrease its value by `2`.
3. If a cell is non-firing and it has **more than 3** firing neighbors, decrease its value by `1`.
4. A cell's value can never go below `0`.
5. In all other cases, the cell keeps its current value.
Implement a function to update the matrix state.
Follow-up:
- First solve it using a copied matrix.
- Then optimize the solution to use `O(1)` auxiliary space.
Quick Answer: This question evaluates competency in matrix/grid manipulation, neighbor-counting logic for eight-directional adjacency, simultaneous state transitions, and space-optimized in-place updates (O(1) auxiliary space).
You are given an `m x n` integer matrix `neurons`.
- A cell is a **firing** neuron if its value is `0`.
- A cell is a **non-firing** neuron if its value is greater than `0`.
For each cell, count the number of firing neighbors among its 8 surrounding cells (horizontal, vertical, and diagonal). All updates must be applied **simultaneously** based on the original state of the matrix.
Update the matrix using these rules:
1. If a cell is firing (`0`) and **exactly 3** of its neighbors are firing, its new value becomes `6`.
2. If a cell is non-firing and it has **0 or 1** firing neighbors, decrease its value by `2`.
3. If a cell is non-firing and it has **more than 3** firing neighbors, decrease its value by `1`.
4. A cell's value can never go below `0`.
5. In all other cases, the cell keeps its current value.
Return the updated matrix.
**Follow-up:** First solve it using a copied matrix, then optimize to use `O(1)` auxiliary space (encode the new state in the original cells using a reversible encoding, then decode in a second pass).
Constraints
- 1 <= m, n <= 300 (matrix may also be empty)
- 0 <= neurons[i][j] (values are non-negative integers)
- A firing neuron has value 0; a non-firing neuron has value > 0
- All updates are computed simultaneously from the original state
- A cell's value can never go below 0
Examples
Input: ([[0, 0, 0], [0, 0, 0], [0, 0, 0]],)
Expected Output: [[6, 0, 6], [0, 0, 0], [6, 0, 6]]
Explanation: All cells firing. Each corner has exactly 3 firing neighbors -> becomes 6. Edge cells have 5 firing neighbors and the center has 8, neither equals 3, so they stay 0.
Input: ([[5]],)
Expected Output: [[3]]
Explanation: A single non-firing cell with 0 firing neighbors (0 or 1) -> decrement by 2: 5 - 2 = 3.
Hints
- Snapshot the original matrix (deep copy) so neighbor counts are computed from the pre-update state, not from values you have already changed.
- A neighbor is 'firing' only if its ORIGINAL value is 0. Check all 8 directions and stay within bounds.
- Apply exactly one rule per cell: firing cells only change (to 6) when the firing-neighbor count is exactly 3; a count of exactly 3 on a non-firing cell falls through to 'keep value'.
- For the O(1) follow-up, encode both old and new state in each cell (e.g. store new_value * K + old_value for a large K), count neighbors using value % K, then divide out in a second pass.