Maximize Fixed Points After Deletions
Real-world version: Most Readings Settled at Their Own SlotThe statement here is our own: the same inputs, outputs and technique.
A log holds the readings nums in the order they were taken. An auditor may delete any readings, including none of them. Deleting a reading closes the gap, so the readings that remain keep their relative order and are renumbered from 0.
A remaining reading is settled when its value equals its slot in the shortened log. Return the largest number of settled readings the auditor can leave behind.
Examples
Example 1
- Input
- nums = [2, 0, 1, 4]
- Output
- 2
Deleting the reading 2 leaves 0, 1, 4 in slots 0, 1 and 2. The readings 0 and 1 then sit at their own slots, so two readings are settled.
Example 2
- Input
- nums = [4, 3, 2, 1, 0]
- Output
- 1
Deleting the first two readings leaves 2, 1, 0 in slots 0, 1 and 2, where none is settled. Deleting the last four leaves 4 alone, which is not settled either. Keeping all five puts the reading 2 in slot 2, which settles one reading.
Example 3
- Input
- nums = [0, 0, 0, 0]
- Output
- 1
Only slot 0 can hold a reading of 0, so at most one reading is settled however many are deleted.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^5
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def most_settled_slots(nums: list[int]) -> int:public int mostSettledSlots(int[] nums)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's