Amazon Online Assessment 2021 (OA) - Good Segment

Think of it like this: On the first day of a special event, everyone is challenged to show their problem-solving skill in programming. Here is what the challenge is about: there are these numbers, let's call them 'bad numbers', and a set of whole numbers in a certain range. Guess what? The task is to figure out the longest sequence of whole numbers in this range that doesn't include any of those 'bad numbers'.

Relevant Amazon OA Problems:

Input

  • bad_numbers: an array of integers
  • lower: an integer, the lower bound, inclusive
  • upper: an integer, the upper bound, inclusive

Output

an integer denoting the length of longest contiguous sequence

Examples

Example 1:

Input:

1bad_numbers = [37,7,22,15,49,60]
2lower = 3
3upper = 48

Output: 14

Explanation:

The segments in the range 3 to 48, inclusive, without any bad numbers are [3,6], [8,14], [16,21], [23,36] and [38,48].

The longest segment is [23,36] and it is 14 elements long, thus the return value is 14.

Constraints

  • 1≤n≤10^5
  • 1≤badNumbers[i]≤10^9
  • badNumbers contains distinct elements

Try it yourself

Solution

←
↑TA 👨‍🏫