Maximum Distinct Integers After ±k Offset

Given an integer array and an offset `k`, you may add to each element any **distinct** integer in `[-k, k]` (each offset value can be used at most once across the whole array). Return the maximum number of distinct values achievable in the resulting array. Requirements Input: array nums = [a₁, …, aₙ] and offset k. Constraints: 1 ≤ n ≤ 100_000, 1 ≤ nums[i] ≤ 1e9, 0 ≤ k ≤ 1e9. For each element you may add any integer in [-k, k] exactly once; offsets are chosen independently per element (they are not required to be distinct across the array). Output: the maximum number of distinct values in the resulting array. Input: nums = [1, 2, 2, 3, 3, 4], k = 2 Output: 6 (e.g. [-1, 0, 1, 2, 3, 4] — all distinct) Input: nums = [4, 4, 4, 4], k = 1 Output: 3 (only {3, 4, 5} are reachable; the 4th element must collide) Notes The naïve O(n × k) solution (try every offset for every element) is rejected — interviewers expect O(n log n) or O(n). The accepted greedy: sort the elements; sweep left-to-right; for each element, assign the smallest unused value in [a_i − k, a_i + k]. With a SortedSet of "used values" the lookup is O(log n) per element. Linear time is reachable if you walk a single moving pointer through the sorted union of windows. The interviewer in this report kept saying "I have a better approach but no time to explain" — be ready to defend whichever solution you ship without expecting useful hints. The distinctness constraint is on the resulting values, not on the offsets: two elements may apply the same offset as long as their results differ (the greedy above relies on distinct results, not distinct offsets). Minority variant: some candidate reports frame it as "each offset in [-k, k] may be used at most once across the whole array" — a stricter, materially different problem. Clarify which rule applies before coding. Preparation Drill the greedy sweep with a SortedSet (from sortedcontainers import SortedSet) — write it in under 15 minutes. Practice articulating why sorting first makes the greedy choice safe (exchange argument: any optimal assignment can be reordered into a sorted sweep without loss). This is a classic high-pressure / low-feedback xAI round — practice narrating tradeoffs aloud even when the interviewer pushes back without specifics.