Pick the fix
Lockers in a ring hold [3, 1, 3]. The row version returns 6. What is wrong?
Choose an answer, then open Show answer below to check it.
Answer: A It opens the first and last lockers, which are neighbours in a ring
Right: the true answer is 3.
Dropping one end per run removes exactly the forbidden pair and nothing else.
In a ring, the first and last lockers cannot both be opened. So solve the straight-row version twice, once without the first locker and once without the last, and take the better result. Each run is O(n), so the total is O(n) time. The two slices take O(n) memory; passing index bounds instead of slices brings it to O(1).
Explain the ring version.
Say your answer out loud, then check which of these points you covered:
Breaking a circular constraint into two straight cases is a reusable trick.
A single locker is a special case: both runs would drop it.
The same split handles circular scheduling and seating questions.
def ring_haul(amounts: list[int]) -> int:
def straight(row: list[int]) -> int:
two_back = one_back = 0
for a in row:
two_back, one_back = one_back, max(one_back, two_back + a)
return one_back
if len(amounts) == 1:
return amounts[0]
return max(straight(amounts[1:]), straight(amounts[:-1]))Explain why two runs cover every valid choice.
Think of your answer first, then open the hint.
Why are two runs enough?
Any valid choice either skips the first locker or skips the last, so one of the runs covers it.
What about a ring where you must open exactly k lockers?
Add k to the state: best[i][j] with j lockers opened, still split into two straight cases.
What each operation costs: Two Dimensional Arrays
From the author
Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.
Suggest a fix if something here is wrong or out of date.