Longest Consecutive Sequence

Interview Problem Interview Medium Array Hash Set Hashing

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.longestConsecutive(nums). Return the length of the longest set of values forming x, x+1, ... in O(n) expected time. Input order is irrelevant.

Starter code

class Solution:
    def longestConsecutive(self, nums):
        pass

Test cases

unordered-run

{
  "args": [
    [
      100,
      4,
      200,
      1,
      3,
      2
    ]
  ]
}

Expected: 4

Wizard outline

Step 1: Initialize Solution.longestConsecutive
Replace the empty starter with the first real state owned by Solution.longestConsecutive. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Empty case
Complete the readable core algorithm for one representative Interview case. Start counting only at values with no predecessor so every sequence is traversed once.
Step 4: Harden the Unordered Run boundary
Repair the reviewed boundary and pass the complete submission contract. Every consecutive sequence has exactly one value with no predecessor. The algorithm starts there and counts every member, so the maximum counted length is exactly the longest sequence.

Footguns and prerequisites

Expanding from every value repeats long sequences and can become quadratic.
hashing and sets

Reviewed references

LeetCode 128 — Longest Consecutive Sequence

Practice prerequisites

Track Previously Seen Values(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing longest consecutive sequence as a complete Interview Problem.

Recommended approach and implementation

Put values in a set; for each value lacking value-1, walk forward until the sequence ends.

Why it works: Every consecutive sequence has exactly one value with no predecessor. The algorithm starts there and counts every member, so the maximum counted length is exactly the longest sequence.

class Solution:
    def longestConsecutive(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        values = set(nums)
        best = 0
        for value in values:
            if value - 1 in values:
                continue
            length = 1
            while value + length in values:
                length += 1
            best = max(best, length)
        return best