Introduction

This problem is usually the longest consecutive interval problem expressed in interval terms. Given a list of integers, find the largest interval L..R such that every integer from L through R appears in the list, and do it in expected O(n) time even when duplicates exist.

Core Observation

Sorting the numbers would make the task easy, but sorting costs O(n log n). To stay linear, use a hash set so membership checks such as "does x + 1 exist?" are expected O(1).

The key trick is to expand intervals only from their starting points. A value x is the start of an interval only when x - 1 is not present.

That one condition prevents repeated work. If 5 is in the middle of the interval 1..8, there is no reason to scan upward from 5 because the scan starting at 1 will already cover it.

Linear-Time Algorithm

The algorithm is:

1. Put every number into a set.
2. For each unique number x, check whether x - 1 is absent.
3. If it is absent, x starts a consecutive run.
4. Walk upward until the next integer is missing.
5. Keep track of the best interval seen so far.

Because each unique number is visited as part of at most one upward scan, the total work stays linear on average.

Python Example

1def biggest_interval(values):
2    if not values:
3        return None
4
5    seen = set(values)
6    best = None
7
8    for x in seen:
9        if x - 1 in seen:
10            continue
11
12        end = x
13        while end + 1 in seen:
14            end += 1
15
16        current = (x, end)
17        if best is None or (current[1] - current[0]) > (best[1] - best[0]):
18            best = current
19
20    return best
21
22
23data = [100, 4, 200, 1, 3, 2, 2, 5, 7, 6]
24print(biggest_interval(data))

Output:

(1, 7)

This means every integer from 1 through 7 is present in the list.

Why Duplicates Do Not Break the Algorithm

The title mentions duplicates, but duplicates are not a special challenge if the question is only about presence. The interval 1..7 is still valid whether the input contains one 4 or six copies of 4.

Using a set removes duplicates automatically. That simplifies the logic and avoids wasted scanning work.

If the task instead asks for a contiguous subarray in the original order, or requires counting repeated values, then this is a different problem entirely.

Why the Time Complexity Is O(n)

At first glance, the while loop looks like it could make the algorithm quadratic. The reason it does not is that the loop runs only for interval starts.

For example, if the set contains 10, 11, 12, 13, only 10 launches a scan. The values 11, 12, and 13 are skipped because their predecessor exists.

So the total cost is:

• 'O(n) to build the set'
• one pass over the unique values
• one upward walk per interval, not per element

That yields expected O(n) time and O(n) extra space.

Returning the Members of the Interval

If you want the actual values instead of just the endpoints, build them afterward:

start, end = biggest_interval([8, 2, 4, 3, 10, 1, 5])
print(list(range(start, end + 1)))

Separating the search from the output formatting keeps the main algorithm simple.

Common Pitfalls

The most common mistake is sorting and then calling the solution linear. Sorting is fine, but it is O(n log n).

Another mistake is expanding upward from every element instead of only from interval starts. That can degrade performance badly on long runs.

People also confuse "largest interval whose members are in the list" with "longest contiguous subarray." This algorithm ignores the original order completely.

Finally, make sure the empty-list case is defined. Returning None or an empty interval is fine, but the behavior should be explicit.

Summary

• Use a hash set to get expected constant-time membership checks.
• Start scanning only from numbers whose predecessor is absent.
• Duplicates do not matter when the question is about presence only.
• The algorithm runs in expected O(n) time with O(n) extra space.
• If order matters, you need a different algorithm than the consecutive-set approach.