# My O(N) idea and is there any other approach?

• First, I will describe my idea.

The straightforward solution would be to sort all the numbers (for example, via std::sort), remove the duplicates, and then just to scan through them with a simple FOR-loop, keeping track of the longest suffix of the current processed numbers which contains only consecutive integers. Taking the maximum of these values, we obtain a simple O(N log N + N) solution.

Actually, the O(N log N) part depends only on sorting. So, considering that all the given numbers are small, one can do a bucket sort, thus, obtaining something like O(K + N), where K is the largest among the given integers.

The smarter solution is based on keeping track of the maximal by inclusion consecutive segments. We can maintain a map A, where A[x] is the other bound of the maximal by inclusion segment, which's one of bounds is equal to x. Then, when a number x arrives, we can look, whether there is any maximal-by-inclusion segment, which has one of bounds equal to x-1 or x+1, and based on this, possibly build a new one, or merge some two maximal-by-inclusion segments of the consecutive numbers. On every iteration (i.e. number addition), we will try to update the answer with the length of the newly calculated maximal-by-inclusion segment.

If we do it with a hash_map, then we obtain O(N) solution, which is required.

But the judge doesn't support hash_map's (at least I wasn't able to use it). So is there any other model solution that doesn't use hashing at all?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.