Update a Neuron Grid
Problem Description
You are given an m x n integer matrix, neurons.
Definitions
- 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 in the matrix, you must count the number of firing neighbors among its 8 surrounding cells (horizontal, vertical, and diagonal). All updates to the matrix must be applied simultaneously, meaning the calculation for every cell's new state must be based entirely on the original state of the matrix before any updates are made.
Update Rules
Apply the following rules to update the matrix:
- If a cell is currently firing (
0) and exactly 3 of its neighbors are firing, its new value becomes6. - If a cell is currently non-firing (value
>0) and it has 0 or 1 firing neighbors, decrease its value by2. - If a cell is currently non-firing (value
>0) and it has more than 3 firing neighbors, decrease its value by1. - A cell's value can never go below
0. If a decrease would result in a negative value, the new value should be0. - In all other cases not covered by rules 1-3, the cell keeps its current value.
Task
Implement a function that takes the neurons matrix and updates its state according to the rules.
Follow-up
- First, solve the problem using a copied matrix to manage the simultaneous updates.
- Then, optimize the solution to use
O(1)auxiliary space.
AI interview prep
Core dilemma
The central engineering conflict is managing state dependencies for simultaneous updates in a grid, specifically the challenge of calculating new states based purely on the *original* state while striving for optimal space complexity (O(1) auxiliary space).
2 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Update a Neuron Grid
Problem Description
You are given an m x n integer matrix, neurons.
Definitions
- 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 in the matrix, you must count the number of firing neighbors among its 8 surrounding cells (horizontal, vertical, and diagonal). All updates to the matrix must be applied simultaneously, meaning the calculation for every cell's new state must be based entirely on the original state of the matrix before any updates are made.
Update Rules
Apply the following rules to update the matrix:
- If a cell is currently firing (
0) and exactly 3 of its neighbors are firing, its new value becomes6. - If a cell is currently non-firing (value
>0) and it has 0 or 1 firing neighbors, decrease its value by2. - If a cell is currently non-firing (value
>0) and it has more than 3 firing neighbors, decrease its value by1. - A cell's value can never go below
0. If a decrease would result in a negative value, the new value should be0. - In all other cases not covered by rules 1-3, the cell keeps its current value.
Task
Implement a function that takes the neurons matrix and updates its state according to the rules.
Follow-up
- First, solve the problem using a copied matrix to manage the simultaneous updates.
- Then, optimize the solution to use
O(1)auxiliary space.
