Ward Handoff Review
Start indices of length-k subarrays with at most max_changes adjacent changes
A hospital ward records the caregiver responsible for each consecutive time slot. The array caregivers contains those caregiver IDs in chronological order.
A review covers exactly k consecutive slots. A handoff occurs whenever two adjacent slots within that review have different caregiver IDs. Changes immediately before or after the review do not count.
Return the zero-based starting indices, in increasing order, of all reviews containing at most max_changes handoffs. Return an empty list if no review qualifies.
Examples
Example 1
Input: caregivers = [4,4,7,7,7,2], k = 4, max_changes = 1 Output: [0,1,2]
The four-slot reviews beginning at indices 0 and 1 each contain one handoff. The review beginning at index 2 contains two handoffs, exceeding the limit.
Example 2
Input: caregivers = [9,3,9], k = 1, max_changes = 0 Output: [0,1,2]
Every review contains only one slot, so none has an adjacent pair and all reviews qualify.
Example 3
Input: caregivers = [1,2,1,2,1], k = 3, max_changes = 1 Output: []
Each pair of consecutive slots has different caregivers. Therefore every three-slot review contains two handoffs, exceeding the allowed one.
Constraints
- 1 <= caregivers.length <= 10000
- 0 <= caregivers[i] <= 1000000
- 1 <= k <= caregivers.length
- 0 <= max_changes <= k - 1
Caregiver IDs are labels, not quantities. Only equality between neighboring IDs matters. The intended solution runs in O(n) time and uses O(1) auxiliary space, excluding the returned list.
Hints
Show hint 1Hint 1
Count handoffs in the first review by comparing its adjacent caregiver IDs.
Show hint 2Hint 2
When a review moves one slot to the right, only one old adjacent pair leaves and one new adjacent pair enters.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Can you produce qualifying indices as a stream without storing the complete result?
- How would you find the longest review containing at most max_changes handoffs if its length were not fixed?
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