Show problems as
Classic problem #2009HardArrayHash TableBinary SearchSliding Window

Minimum Number of Operations to Make Array Continuous

Real-world version: Restencilling Bins Into a Consecutive Run
Tracked in this browser only
Read Minimum Number of Operations to Make Array Continuous on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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

Python
def min_restencils(codes: list[int]) -> int:
Java
public int minRestencils(int[] codes)

More on the same topics