Culture Tray Clearance Rounds
Removal round for each array element smaller than its current left neighbor
A genetics lab places cultures in a single row. Each culture has a signed, calibrated activity reading recorded in activity.
The lab repeatedly performs clearance rounds. At the start of each round, every culture except the leftmost remaining culture compares its reading with that of its immediate remaining neighbor to the left. If its own reading is strictly smaller, it is marked for removal. All marked cultures are then removed simultaneously. Equal readings do not trigger removal.
Rounds are numbered starting from 1. The process stops when a round would remove nothing.
Return an integer list in the original culture order. For each culture, report the round in which it is removed, or 0 if it remains when the process stops. An empty row produces an empty list.
Examples
Example 1
Input: activity = [9,2,4,3,6] Output: [0,1,2,1,3]
In the first round, the cultures with readings 2 and 3 are removed. The remaining row is [9, 4, 6]. The culture with reading 4 is removed in the next round, exposing the culture with reading 6 to the culture with reading 9.
Example 2
Input: activity = [1,1,3,5] Output: [0,0,0,0]
The readings never decrease from left to right. Equal neighbors are allowed, so no culture is removed.
Example 3
Input: activity = [-2,-4,-3] Output: [0,1,2]
The culture with reading -4 is removed first. Only after that removal does the culture with reading -3 have a strictly larger immediate neighbor to its left.
Constraints
- 0 <= activity.length <= 8000
- -10^9 <= activity[i] <= 10^9
- All removal decisions within a round use the row as it existed at the start of that round.
The intended solution takes O(n) time and O(n) space. Removal rounds refer to original indices, not positions in the shrinking row.
Hints
Show hint 1Hint 1
Processing every round explicitly can be quadratic: one removal may expose exactly one new culture for the next round.
Show hint 2Hint 2
Scan left to right with a stack of readings and removal rounds. When bypassing readings no larger than the current reading, track the greatest removal round among them before deciding when the current culture can be removed.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you obtain the total number of nonempty clearance rounds from the returned list?
- How would the stack comparisons change if a culture were removed when its reading was strictly larger than its left neighbor's?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem