Time to Stabilize - Find Steps Until System State Stops Changing

Question

## Problem

A cellular automaton starts with an array of integers. At each step, every element is replaced by the sum of its neighbors (not including itself). An element at index 0 or `n-1` has only one neighbor. The system "stabilizes" when no element changes between two consecutive steps (or when a cycle is detected).

Return the number of steps until stabilization, or `-1` if it does not stabilize within `max_steps`.

```python
def time_to_stabilize(
    state: list[int],
    max_steps: int
) -> int:
```

## Example

```
state = [1, 0, 0]
Step 1: [0, 1, 0]
Step 2: [1, 0, 1]
Step 3: [0, 2, 0]
# oscillates -> returns -1 if max_steps is small

state = [0, 0, 0]
Step 1: [0, 0, 0]  -> stabilizes immediately
Output: 0
```

## Follow-ups

1. How do you detect a cycle (the state has been seen before) to return early instead of running `max_steps` iterations?
2. What data structure lets you check for repeated states efficiently when the state is a large array?
3. Extend to a 2D grid where each cell sums its 4 cardinal neighbors.
4. What is the time and space complexity of your cycle-detection approach?

Time to Stabilize - Find Steps Until System State Stops Changing

Question Details

Full Details

Topics

More from Amazon