The O(n) Club: Longest Consecutive Sequence: Arrays, Coffee, and Why HashSets Are Your Real Friends

The O(n) Club: Longest Consecutive Sequence — Arrays, Coffee, and Why HashSets Are Your Real Friends

⚡ TL;DR

Unsorted array, need the longest consecutive sequence. Brute force? O(n²)—as enjoyable as a Monday morning. Use a HashSet and win in O(n):

// Java one-liner version
Set
<integer> set = new HashSet<>();
for (int num : nums) set.add(num);
int best = 0;
for (int num : set) {
    if (!set.contains(num - 1)) {
        int streak = 1;
        while (set.contains(num + streak)) streak++;
        best = Math.max(best, streak);
    }
}</integer>

🧠 How Devs Usually Mess This Up

First, they think “consecutive” equals “adjacent” (spoiler: it doesn’t). That sends them sorting things or walking the array line-by-line, as if the universe sorted real data for your convenience. Next, they make things worse by testing every number as a possible sequence start, even if someone already counted it. Extra points if you ignore duplicates—you’ll get random surprises in your answer and ancient CPU fans howling at 2 am.

🔍 What’s Actually Going On

Picture your input as a bunch of caffeine-addled conference-goers wandering around. Put everyone’s badge in a Set (no double entries, because one awkward encounter is enough). Now, only start a streak when a person’s badge doesn’t have their left neighbor (so sequence only starts at the beginning). If someone’s badge number is the start of a group (nobody with num-1), walk forward (num+1, num+2, …), and count the group. Classic introvert efficiency: only count from the lonely ones.

🛠️ PseudoCode

• Add numbers to a HashSet.

  Set<Integer> set = new HashSet<>();
  for (int num : nums) set.add(num);

  It’s like herding cats, but faster.
• Loop over each unique value:

  for (int num : set) { ... }

  Because arrays invite drama. Sets run the show.
• Only start if no left neighbor:

  if (!set.contains(num - 1))

  If num-1 isn’t around, num is a true sequence starter.
• Expand forward:

  int streak = 1;
  while (set.contains(num + streak)) streak++;

  Count as far right as the clique lasts.
• Track best streak:

  best = Math.max(best, streak);

  Not all streaks are created equal. Only the best one gets you the job.

💻 The Code

public int longestConsecutive(int[] nums) {
    Set
<integer> set = new HashSet<>();
    for (int num : nums) set.add(num);
    int best = 0;
    for (int num : set) {
        if (!set.contains(num - 1)) {
            int streak = 1;
            while (set.contains(num + streak)) {
                streak++;
            }
            best = Math.max(best, streak);
        }
    }
    return best;
}
</integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Consecutive ≠ adjacent: The numbers can be anywhere, like socks after laundry.
• Forgot to deduplicate? Expect sketchy results and endless loops. Sets: not just for bug-fixing, but for life.
• Attempting streaks everywhere: Don’t start counting if num-1 exists, unless you like wasting cycles.
• Time/Space reality check: O(n) time, O(n) space. Sorry, you can’t out-clever the interview math.

🧠 Interviewer Brain-Tattoo

“HashSet is basically a door bouncer: only lets you in once, blocks drama, and knows exactly where everyone is. Use it.”