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.
Overview: 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.
Community answers
Answer by arokyzxc
def updateNeuronGridCopy(neurons):
if not neurons or not neurons[0]:
return
m, n = len(neurons), len(neurons[0])
# Create a deep copy of the original grid to read from
copy_grid = [row[:] for row in neurons]
# 8-directional offsets
directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
for r in range(m):
for c in range(n):
# Count firing neighbors (value == 0 in the original state)
firing_neighbors = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and copy_grid[nr][nc] == 0:
firing_neighbors += 1
# Apply rules based on copy_grid, update neurons in-place
current_val = copy_grid[r][c]
if current_val == 0: # Firing
if firing_neighbors == 3:
neurons[r][c] = 6
else: # Non-firing (> 0)
if firing_neighbors <= 1:
neurons[r][c] = max(0, current_val - 2)
elif firing_neighbors > 3:
neurons[r][c] = max(0, current_val - 1)
# "All other cases" remain unchanged