Longest Consecutive Sequence

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given unsorted numbers in an array, find the longest consecutive sequence

Why This Works

(Explain the core reason the solution is correct.)

• Set dedupes everything
• Set has $O(1)$ lookup
• Check left item to avoid re-checking same items

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Hash Map
• Sets

Time & Space Complexity

• Time: $O(n)$ → Reason: Will iterate over every unique item once
• Space: $O(n)$ → Reason: If all items are unique, will store everything just once

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        mySet = set(nums)
        longestSequence = 0

        for num in mySet:
            if (num - 1) in mySet:
                continue
            else:
                currentSequence = 0
                currentNum = num
                while currentNum in mySet:
                    currentSequence += 1
                    currentNum += 1
                longestSequence = max(longestSequence, currentSequence)

        return longestSequence

Common Mistakes / Things I Got Stuck On

• Looped against nums. If it has duplicates you could be doing $n^2$ operations. Therefore, iterate on the set mySet