0842HardArrayBinary SearchSorting

Most Readings Settled at Their Own Slot

Tracked in this browser only

Trains the technique from

LeetCode 3920Maximize Fixed Points After Deletions

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def most_settled_slots(nums: list[int]) -> int:

Java

public int mostSettledSlots(int[] nums)

The intended approach

Time O(n log n) for n readings: one sort, then one Fenwick query and update per reading.Space O(n) for the filtered readings and the Fenwick tree.

Deleting readings moves a survivor earlier and never later, so a reading can only settle at a slot no greater than its own value; call the difference between its original slot and its value its slack, and drop every reading whose slack is negative. Two settled readings need as many survivors between them as the gap between their slots, and the readings originally between them are exactly what is available, which holds precisely when the slack does not decrease from the earlier to the later one. So the answer is the longest run of readings whose values strictly increase and whose slack never decreases. Sort by value and sweep the equal-value groups in turn, asking a Fenwick tree over slack for the best run ending at a smaller value with no more slack, and inserting a whole group only after the group has been answered so no two readings of the same value chain together.

Pythonentry point: most_settled_slots

def most_settled_slots(nums):
    # a reading can only settle at a slot no larger than its own value, since
    # deleting moves it earlier and never later. Two settled readings need enough
    # survivors between them to fill the gap, which is exactly the condition that
    # their slack -- index minus value -- never decreases along the run.
    items = []
    for idx, value in enumerate(nums):
        if value <= idx:
            items.append((value, idx - value))
    if not items:
        return 0

    slacks = sorted({slack for _v, slack in items})
    rank = {s: i + 1 for i, s in enumerate(slacks)}
    size = len(slacks)
    tree = [0] * (size + 1)

    def best_upto(i):
        out = 0
        while i > 0:
            if tree[i] > out:
                out = tree[i]
            i -= i & (-i)
        return out

    def put(i, val):
        while i <= size:
            if tree[i] < val:
                tree[i] = val
            i += i & (-i)

    items.sort()
    answer = 0
    pos = 0
    total = len(items)
    while pos < total:
        end = pos
        while end < total and items[end][0] == items[pos][0]:
            end += 1
        # settle the whole equal-value group against earlier values only, so no
        # two readings of the same value ever land in the same run
        fresh = []
        for value, slack in items[pos:end]:
            length = best_upto(rank[slack]) + 1
            fresh.append((rank[slack], length))
            if length > answer:
                answer = length
        for r, length in fresh:
            put(r, length)
        pos = end
    return answer

The obvious version

Try every set of readings to keep, largest sets first, renumber what remains and count how many sit at their own slot. Exponential, but it makes no argument about which readings are worth keeping.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_most_settled_slots(nums):
    import itertools
    n = len(nums)
    best = 0
    for size in range(n, -1, -1):
        if size <= best:
            break
        for keep in itertools.combinations(range(n), size):
            left = [nums[i] for i in keep]
            hits = 0
            for pos in range(len(left)):
                if left[pos] == pos:
                    hits += 1
            if hits > best:
                best = hits
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in