Problem statement

https://leetcode.com/problems/longest-consecutive-sequence/

Solution

One possible solution is to use Union Find, where we keep different sets of consecutive numbers and if needed, we update it, this can be done in O(n) both time and memory, however it is a bit difficult to implement.

More simple way is to keep all numbers in set, and then try to find the longest group, because we have a quick way to check if given number inside our set or not. Imagine, that we have numbers 1, 100, 2, 3, 101, 6, 5, 4 and let us go through the steps of our algorithm to see how it works. The idea is always start with the start of our groups, that is if we have num - 1 in our set, we ignore this number and go to the next.

  1. num = 1, we check num - 1 = 0 is inside our set? No, so we do nothing. Next step is to check if 2 is here, then if 3 is here, and so on. In this example we will reach 6, it means that we found group with length 6, so we can update our answer.
  2. num = 100, we check if 99 is here, it is not. Then we check 101, 102 and so on. We found group with 2 elements here.
  3. num = 2, check if 1 is here, yes - it is, so we do nothing, it is not the start of our group!
  4. num = 3, 101, 6, 5, 4 are all ignored, because it is not the start of the group.

Complexity

Even though we have while inside for loop, time complexity is linear: in fact we will work with each number at most twice. If we have consecutive sequence a, ..., b, then we have one pass over data when we work with number a and for each number from a+1 to b we just check in O(1) if previous number is here. Space complexity is O(n) as well to keep our set of numbers.

Code

class Solution:
    def longestConsecutive(self, nums):
        set_nums, ans = set(nums), 0
        for num in nums:
            if num - 1 in set_nums: continue
                
            nxt = num
            while nxt + 1 in set_nums:
                nxt += 1
            ans = max(ans, nxt-num+1)
                
        return ans