Longest segment of integers excluding bad numbers
Filed under BNY Mellon
Free read 1 of 3Confirm whether the range bounds L and R are inclusive and if bad numbers can lie outside [L, R].
The question
Given an array of bad numbers and a range defined by [L, R], determine the length of the longest contiguous segment of valid integers within the range [L, R] that contains no bad numbers.
Constraints
- 0 <= length of bad numbers array <= 10^5
- L <= R, with values up to 10^9
Examples
- Input
- bad = [3, 7], L = 1, R = 10
- Output
- 5
- Why
- Valid ranges formed by excluding 3 and 7 from [1, 10] are [1, 2], [4, 6], [8, 10]. The longest has length 3 (e.g., [4, 5, 6] or [8, 9, 10]), wait, let's check: 4 to 6 is length 3, 8 to 10 is length 3. If bad=[3], segments are [1,2] (len 2) and [4,10] (len 7).
Approach
Confirm whether the range bounds L and R are inclusive and if bad numbers can lie outside [L, R].
Iterate through every integer from L to R, check if it is in the bad numbers set, and track the maximum consecutive valid integers.
Filter bad numbers to only those within [L, R], sort them, and find the maximum gap between consecutive bad numbers (plus boundary checks with L-1 and R+1).
No bad numbers in range (result is R - L + 1); all numbers in range are bad (result is 0).
Tips
- What they are testing: Tests when all numbers are bad, no numbers are bad, or bad numbers fall outside the [L, R] range.
- Common mistake: Failing to sort the bad numbers array before processing intervals.
Related BNY Mellon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.