0648HardArrayHash TableBinary SearchSliding Window

Restencilling Bins Into a Consecutive Run

Tracked in this browser only

Trains the technique from

LeetCode 2009Minimum Number of Operations to Make Array Continuous

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 stockroom holds n bins, and codes[i] is the integer stencilled on bin i. The manager wants the stencils tidy, which means both of these hold:

no two bins carry the same code;
the largest code is exactly n - 1 above the smallest.

In other words the n codes become n consecutive integers, in any arrangement across the bins.

One operation picks a single bin and restencils it with any integer you choose; the new code is not restricted to the range the original codes came from. The bins themselves are never added or removed.

Return the least number of operations that makes the stencils tidy.

Examples

Example 1

Input: codes = [9, 4, 5, 6]
Output: 1

Restencilling the bin marked 9 as 7 leaves the codes 7, 4, 5, 6: four different codes whose smallest is 4 and whose largest is 7, which is 3 above it. That is one operation.

Example 2

Input: codes = [7, 7, 7, 7]
Output: 3

All four bins carry the same code. Restencilling three of them as 8, 9 and 10 leaves 7, 8, 9, 10, which is tidy, and that is three operations.

Example 3

Input: codes = [2, 2, 3, 4, 4, 7]
Output: 2

Restencilling one bin marked 2 as 5 and one bin marked 4 as 6 leaves the codes 2, 5, 3, 4, 6, 7: six different codes running from 2 up to 7, which is 5 above it. That is two operations.

Constraints

1 <= codes.length <= 10^5
1 <= codes[i] <= 10^9

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 min_restencils(codes: list[int]) -> int:

Java

public int minRestencils(int[] codes)

The intended approach

Time O(n log n): the sort dominates; the window pass is linear.Space O(n) for the sorted distinct codes.

Every operation is free to write anything, so the work is to decide which bins keep their current code. The kept codes must be distinct and must all fit inside one run of `n` consecutive integers, so repeats are useless: reduce the codes to their distinct values and sort them. Then slide a window over that sorted list keeping the difference between its ends at most `n - 1`, advancing the left edge whenever the window grows too wide. The widest window is the most bins that can be left alone, and the answer is `n` minus that.

Pythonentry point: min_restencils

def min_restencils(codes):
    # Bins that already carry a code inside the chosen run of n consecutive
    # integers can stay, and only distinct codes can stay together, so sort the
    # distinct codes and slide a window of span n - 1 over them.
    # O(n log n) time, O(n) space.
    n = len(codes)
    distinct = sorted(set(codes))
    keep = 0
    left = 0
    for right in range(len(distinct)):
        while distinct[right] - distinct[left] > n - 1:
            left += 1
        if right - left + 1 > keep:
            keep = right - left + 1
    return n - keep

The obvious version

Any run of `n` consecutive integers can be shifted upwards until its lowest value coincides with the smallest code it keeps, without losing anything it kept, so it is enough to try each distinct code as the bottom of the run. For each of them, scan all the distinct codes and count how many land inside the run; the best count gives the answer.

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_min_restencils(codes):
    n = len(codes)
    values = sorted(set(codes))
    keep = 0
    for low in values:
        high = low + n - 1
        hits = 0
        for v in values:
            if low <= v and v <= high:
                hits += 1
        if hits > keep:
            keep = hits
    return n - keep

How this problem was checked

Reference solution executed against 12 test cases — 12 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