711. How Many Can Be Nudged Into Agreement
Each value may be replaced ONCE by any value within k of it, that is, anything in
[v - k, v + k]. A value may also be left alone. Print the largest number of values that can
end up EQUAL.
4 6 1 2, k = 2 -> 3 4, 6 and 2 can all become 4
1 3 5 7, k = 2 -> 3
2 2 8 8, k = 3 -> 4
1 100, k = 1 -> 1
## Two values can agree exactly when they are within 2k
v can reach anything in [v - k, v + k], and u anything in [u - k, u + k]. Those two
ranges overlap exactly when
|v - u| <= 2k
and a whole SET can agree on one value exactly when its largest and smallest differ by at most
2k, because then the common target can be any value in the overlap of them all.
Getting from "each value moves by up to k" to "the set spans at most 2k" is the step, and
using k instead of 2k is the mistake this problem is built to catch.
## Sorting makes the set contiguous
Which values are chosen has nothing to do with their order, and the span of a set depends only on its smallest and largest. So sort: any value lying between two chosen values is already inside the span and adding it is free.
A subset problem becomes a window problem, the same move as problem 693.
## The sweep
sort a
for hi in 0 .. n-1:
while a[hi] - a[lo] > 2k: lo += 1
best = max(best, hi - lo + 1)
The condition uses only the two ends, so a plain index pair is enough. No deque is needed here, unlike problem 698, because sorting has already made the window maximum and minimum sit at its edges.
## Boundaries
k = 0 gives the count of the commonest value. A k large enough to span the whole array
gives n. A single value answers 1.
## Overflow
Two quantities are worth bounding. The span 2k reaches 2 * 10^9 when k is 10^9,
and the difference a[hi] - a[lo] stays under 10^9 because every value is at most
10^9. A signed 32 bit integer holds up to 2147483647, so both FIT, the larger with
about seven percent to spare. This problem has no overflow.
The reference solutions still read k into a 64 bit variable. That costs nothing and means
2 * k cannot surprise anyone who later raises the limit, but the half that matters is
doing the arithmetic instead of assuming a doubled billion must be too big.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 10^9` - `1 ≤ each value ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the largest number of values that can be made equal.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.