How to Explain Longest Consecutive Sequence in a Coding Interview (Step-by-Step)

Longest Consecutive Sequence has a deceptively simple goal, but the optimal solution requires one non-obvious insight: only start counting from the beginning of a sequence. Miss that, and you’re writing O(n log n). Nail it, and you’ve got O(n).

In this post, you’ll learn exactly how to walk an interviewer through LeetCode 128 — from the brute-force pitfall to the HashSet approach, the sequence-start trick, and a clear complexity argument.

Problem Statement

Examples

Constraints

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

What Is the Problem?

“I’m given an unsorted array of integers and I need to find the length of the longest run of consecutive integers — where consecutive means each number is exactly 1 more than the previous one. The order in the array doesn’t matter. I need to do this in O(n) time, which rules out sorting.”

Emphasising the O(n) constraint immediately is important — it signals to the interviewer that you’ve read the problem carefully and you know sorting is off the table.

Step 1: Compare Approaches Before Jumping to Code

“Sorting gives O(n log n) which violates the constraint. The trick to hitting O(n) is using a HashSet — it gives us O(1) membership checks. Then we need one more insight to avoid redundant counting.”

The Key Insight — Only Start at Sequence Beginnings

“If I didn’t have this check, I’d restart a streak count from every element — so for the sequence [1,2,3,4], I’d count 4 streaks from 1, 3 from 2, 2 from 3, and 1 from 4. That’s O(n²) in the worst case. By skipping any number whose predecessor exists in the set, I only ever start a count from the true beginning of a sequence.”

Step 2: Explain the Algorithm in Plain English

Sequence Visualised — nums = [100, 4, 200, 1, 3, 2]

Here’s what happens when we scan the set. Numbers with no left neighbour in the set become sequence starters (blue); numbers that extend a streak are highlighted; those skipped because their predecessor exists are dimmed.

Result: the maximum streak seen is 4, from the sequence [1, 2, 3, 4].

Step 3: Talk Through the Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)   # O(n) build — O(1) lookups from here on
        longest = 0

        for num in num_set:
            # Only start counting if this is the beginning of a sequence.
            # A number is a start if its left neighbour does NOT exist.
            if num - 1 not in num_set:
                current = num
                streak  = 1

                # Walk upward while consecutive numbers exist
                while current + 1 in num_set:
                    current += 1
                    streak  += 1

                longest = max(longest, streak)

        return longest

Point out that we iterate over num_set, not nums. This means duplicates are never visited twice. The inner while loop looks expensive, but across the entire outer loop each number is entered as current at most once — so the total number of while iterations across all outer iterations is at most n, giving O(n) overall.

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

“The inner while loop looks like it could make this O(n²), but it can’t. Each element is consumed by the while loop at most once across all outer iterations. Think of it as amortised — the total number of while steps summed across all outer iterations is bounded by n. So the overall time complexity is O(n).”

Interview Checklist for Longest Consecutive Sequence

• Restate — “find the longest run of consecutive integers; order in the array doesn’t matter”
• Call out the O(n) constraint immediately — explain why sorting is ruled out
• Propose the HashSet approach and explain why it enables O(1) lookups
• State the key insight — only start counting from numbers with no left neighbour in the set
• Explain why skipping non-starts prevents O(n²) inner loop behaviour
• Iterate over the set, not the array — avoid revisiting duplicates
• Call out edge cases — empty input, all duplicates, negatives, disjoint sequences
• Justify O(n) time amortised — each element enters the while loop at most once
• State O(n) space for the HashSet
• Ask clarifying questions before coding — can numbers be negative? can there be duplicates?

Related Problems to Practice

If you can solve Longest Consecutive Sequence cleanly, try these next: