Stabilizing a Row of Student Scores
A row of students sit next to each other, each with an initial integer test score. Implement the function stabilize(A), where you are given a zero-indexed array $A$ of $N$ scores. Each day, every interior student's score updates simultaneously by the following rule, based on the CURRENT day's scores:
- If a student sits immediately between two students with strictly higher scores, that student's score increases by 1.
- If a student sits immediately between two students with strictly lower scores, that student's score decreases by 1.
- The first and last students never change.
The process repeats each day as long as at least one score changes. Return the final stable scores in order as a list.
Constraints
- $1 \le N \le 1000$
- Scores are between 0 and 1000
Example
stabilize([1, 6, 3, 4, 3, 5]) -> [1, 4, 4, 4, 4, 5]
Day 1 gives $[1, 5, 4, 3, 4, 5]$ and day 2 gives $[1, 4, 4, 4, 4, 5]$, after which no score changes, so that is the stable result.
Hints
- Read the update rule carefully: all interior students update at once, based on the same starting configuration each day.
- Use a separate output array per day so you never compare against values you have already modified.
- Loop until a full pass makes no change; bounded scores guarantee the process converges in finitely many days.
Worked Solution
How to Think About It: The key trap is the word "simultaneously": each day's updates must be computed from a snapshot of the previous day, not from values you are mutating in place mid-row. Get that right and the rest is a straightforward simulate-until-no-change loop. Each interior score moves at most toward its neighbors, and since scores are bounded in $[0, 1000]$ and $N \le 1000$, the number of days is bounded, so simulation terminates quickly.
Algorithm: Loop: build a fresh copy of the array; for each interior index compare against the old neighbors and apply $+1$, $-1$, or no change; if nothing changed this pass, stop. The first and last entries are copied unchanged.
Code: ```python def stabilize(A): # Simulate the daily score updates until no score changes, then return # the final stable scores. Each day's updates use a SNAPSHOT of the # previous day (simultaneous update). Endpoints never change. A = list(A) changed = True while changed: changed = False new = A[:] for i in range(1, len(A) - 1): if A[i-1] > A[i] and A[i+1] > A[i]: new[i] = A[i] + 1 changed = True elif A[i-1] < A[i] and A[i+1] < A[i]: new[i] = A[i] - 1 changed = True A = new return A ```
Complexity: $O(N)$ per day; the number of days is bounded by the score range, giving $O(N \cdot R)$ worst case where $R$ is the score spread.
Answer: The function is named stabilize(A). Simulate day by day using a snapshot of the previous scores, stopping when a full pass produces no change, then return the final list.
Intuition
The single most common mistake here is in-place mutation, which makes student $i$'s update depend on student $i-1$'s already-updated value -- a different (and wrong) dynamic. This snapshot-vs-in-place distinction is exactly the bug that haunts cellular-automata, game-of-life, and any parallel-update simulation, including some signal/feature pipelines where everyone updates from the same prior state. Several candidates reported their code failing the platform's hidden tests for precisely this reason.