Stabilizing a Row of Student Scores
Students sit next to each other in a row, 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 rules, using the scores from the START of that day (every update reads the same snapshot, so nobody sees a neighbor's new score until the next day):
- 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. The total gap between neighbors strictly shrinks on any day something moves, which guarantees convergence in finitely many days.
Worked Solution
How to Think About It: The key trap is the word "simultaneously": every update on a given day must be computed from the same start-of-day snapshot, not from values you are mutating in place mid-row. Get that right and the rest is a straightforward simulate-until-no-change loop. Termination is not obvious but follows from a potential argument on the total variation of the row (see Complexity below), so the loop always ends.
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. For the day count, use the potential $V = \sum_{i=0}^{N-2} |A_{i+1} - A_i|$. Two neighbors can never both be strict local minima, nor both strict local maxima, so on every edge the gap either shrinks or stays put, and any day on which something moves shrinks $V$ by at least $1$. The process therefore stops after at most $V \le (N-1)R$ days, where $R$ is the score range, for a total cost of $O(N \cdot D)$ with $D$ the number of days. Note that $D$ is *not* bounded by $R$ alone: alternating scores $[0, 1, 0, 1, \ldots]$ across $1000$ students have range $R = 1$ but take $499$ days to settle.
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.