Longest sequence whose neighbours differ by less than k

A variant of longest consecutive sequence. Given an unsorted array of integers and a positive k, pick distinct values from the array and arrange them in increasing order so that each neighbouring pair differs by less than k. Return the greatest length such a sequence can have. Duplicates in the array don't make it longer.

Interface

Unless you agree on a different interface with the interviewer, assume:

• longest_bounded_gap(nums: list[int], k: int) -> int

Example

longest_bounded_gap([10, 1, 3, 3, 7, 6, 20], 3)  ->  2    # distinct sorted: 1 3 6 7 10 20; runs 1-3 and 6-7
longest_bounded_gap([10, 1, 3, 3, 7, 6, 20], 4)  ->  5    # 1 3 6 7 10
longest_bounded_gap([5, 5, 5], 1)                ->  1
longest_bounded_gap([], 3)                       ->  0

Constraints

• 0 <= len(nums) <= 2 × 10^5; -10^9 <= nums[i] <= 10^9; 1 <= k <= 10^9.

Clarifying questions

• Strictly less than k, or at most k?
• Do duplicates count toward the length?
• With k = 1, is the answer always 1 for a non-empty array? (Yes: distinct integers differ by at least 1.)

What a strong answer covers

• Skipping a value never helps, since it only widens a gap, so the answer is the longest run of sorted distinct values whose gaps are all under k.
• Deduplicate, sort, one scan: O(n log n) time.
• How this generalizes the classic k = 2 case, and why the O(n) hash-set trick for that case doesn't carry over directly.
• Tests: empty, all equal, every gap too big.

Follow-ups

• Return the sequence itself.
• O(n) expected time using buckets of width k.
• Values arrive in a stream: keep the answer up to date.