Longest Consecutive Sequence: Hash Set Pattern

Learning Outcome

After this lesson, you should be able to use a hash set to detect sequence starts and avoid repeated expansion.

Problem Statement

Given an unsorted integer array, return the length of the longest consecutive sequence.

Brute Force Approach

Sort the array and scan consecutive groups. This works, but sorting costs extra time.

Optimized Approach

Put every number in a set. Only start expanding from x when x

• 1 is absent, because that means x is the beginning of a sequence.

Exact Pseudocode

seen = set(nums)
best = 0
for x in seen:
  if x - 1 is not in seen:
    length = 1
    while x + length is in seen:
      length += 1
    best = max(best, length)
return best
  

Reference Code

class Solution:
    def longestConsecutive(self, nums):
        seen = set(nums)
        best = 0

        for x in seen:
            if x - 1 not in seen:
                length = 1
                while x + length in seen:
                    length += 1
                best = max(best, length)

        return best
  

Sample Dry Run

Complexity

Edge Cases

• Duplicates should not extend a sequence twice.
• An empty array returns 0.
• Negative numbers work the same as positive numbers.

Interview Checklist

• Check x

  • 1 before expanding.
• Iterate over the set, not necessarily the original array.
• Do not sort if the target is linear time.

FAQs

If x

• 1 exists, then x belongs to a sequence that already starts earlier.

Every number is part of at most one successful expansion chain.

Hash set lookup with sequence-start detection.