{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Longest Consecutive Sequence – Solution & Complexity

Interview solutions
/
Longest Consecutive Sequence

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • Find the length of the longest run of consecutive integers present in nums (order in the array doesn't matter, only which values exist).
    • The obvious approach — sort, then scan for runs — works and is easy to explain, but costs O(n log n).
    • The problem explicitly asks for O(n), which rules out sorting and requires a hash-set-based approach instead.

  2. Step 2: Hash Set + "Start of Sequence" Check

    • Put every number into a hash set for O(1) membership checks.
    • For each number x in the set, only try to extend a sequence starting at x if x - 1 is not in the set — that means x is the smallest element of its consecutive run, so it's a valid starting point.
    • This guarantees each run is only walked once (from its start), not once per element in it, which is what keeps the overall algorithm O(n) despite the inner while loop.

  3. Step 3: Extending Each Run

    • From a valid start x, keep checking x + 1, x + 2, ... as long as they're in the set, counting the run's length.
    • Track the maximum run length seen across all valid starting points.
    • Because every element is visited at most twice total (once as a candidate start check, once while extending a run it belongs to), the total work across all iterations stays linear.

  4. Step 4: Final Solution (all languages)

    O(n) time (each element examined a constant number of times) and O(n) space for the hash set — meets the problem's stated time complexity requirement.

    def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    best = 0
    for x in num_set:
        if x - 1 not in num_set:
            length = 1
            while x + length in num_set:
                length += 1
            best = max(best, length)
    return best

  5. Step 5: Common mistakes & interviewer follow-ups

    • Forgetting the x - 1 not in num_set guard and extending from every element — still produces the correct answer, but degrades to O(n^2) worst case (e.g. one big consecutive run) since every element re-walks the whole run.
    • Using a sorted approach when O(n) is explicitly required — mention the tradeoff even if you start there, then optimize to the hash-set version.
    • Follow-ups: how would you also return the actual sequence, not just its length? How does the approach change if duplicates should count once (the hash set already handles this for free)?

FAQ

See also

Practice Longest Consecutive Sequence online (run code in the browser)3Sum solution (medium)Contains Duplicate solution (easy)Group Anagrams solution (medium)Majority Element solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?