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


  • 0
    Z

    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?


  • 0

Log in to reply
 

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