Ctrl K

A Run With No Gaps

Hard
You get an integer array values of length n. Call it **solid** if all its numbers are distinct and, once sorted, they follow one another with no gaps, meaning the maximum minus the minimum equals n - 1. For example, [6, 4, 5, 7] is solid and [1, 2, 4] is not. In one operation you may replace any element with any integer. Return the smallest number of operations that makes the array solid.
Example 1
values=[3, 8, 4, 4, 6] → 2

Replace the second 4 with 5 and the 8 with 7: you get [3, 7, 4, 5, 6], the numbers 3 through 7 with no repeats.

Example 2
values=[1, 100, 200] → 2

Any two of the three numbers are too far apart, so only one can stay.

Example 3
values=[10] → 0
Constraints
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁹
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsMedian of Window Variety HardTwo Separate Segments With a Given Sum MediumTrim the Ends to a Target MediumSame-Value Run After Removals MediumMoving Window Median Hard
loading Python…
Input
values=[3, 8, 4, 4, 6]
Expected
2

Run checks the first 3 tests in your browser. Submit checks all 134 tests on the server, hidden ones included.