Longest Consecutive Sequence: HashSet, Expand Each Potential Start

• Longest Consecutive Sequence – find the length of the longest run of consecutive integers in an unsorted array.
• HashSet – provides O(1) membership checks and automatic deduplication.
• True start – a number whose predecessor (value minus one) is not in the set; only true starts begin an expansion.
• Forward expansion – from a true start, count how many consecutive successors are present.
• Time – O(n) because each number is touched at most twice across all expansions.
• Space – O(n) for the set.

What is the Longest Consecutive Sequence problem?

Given an unsorted array of integers, find the length of the longest run of consecutive integers. For example, in [100, 4, 200, 1, 3, 2] the longest consecutive sequence is [1, 2, 3, 4] with length 4. The constraint is that the algorithm must run in O(n) time, ruling out a sort-first approach.

package com.bank.dsa;

public class ConsecutiveSequenceFinder {
    public int longestConsecutive(int[] nums) {
        // implementation below
        return 0;
    }
}

How does the HashSet approach work?

First, add all numbers to a HashSet, which provides O(1) contains checks and automatically removes duplicates. Then scan each number in the set. For each number, check if its predecessor (value minus one) is in the set. If the predecessor is present, this number is in the middle of a run; skip it. If the predecessor is absent, this number is a true start. From the true start, count forward: check for value, value plus one, value plus two, and so on, until the chain breaks.

package com.bank.dsa;

import java.util.HashSet;
import java.util.Set;

public class ChequeSerialAnalyser {
    public static int longestConsecutive(int[] serials) {
        Set<Integer> set = new HashSet<>();
        for (int s : serials) set.add(s);

        int maxLength = 0;
        for (int num : set) {
            // Only start from a true start
            if (!set.contains(num - 1)) {
                int current = num;
                int length = 1;
                while (set.contains(current + 1)) {
                    current++;
                    length++;
                }
                maxLength = Math.max(maxLength, length);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] serials = {100, 4, 200, 1, 3, 2};
        System.out.println("Longest run: " + longestConsecutive(serials));
    }
}

Longest run: 4

Why is this O(n) and not O(n squared)?

The nested while loop looks quadratic at first glance, but the start-only guard ensures that the inner loop runs only for true starts. Across all true starts, each number is expanded through exactly once, so the total inner-loop work is O(n). Combined with the O(n) outer scan, the whole thing is O(n). Each number is touched at most twice: once in the outer scan and once in a single inner expansion.

Amortised analysis:
  Outer scan: visits each number once          = O(n)
  Inner expansion: each number expanded once    = O(n) total
  Total: O(n) + O(n) = O(n)

How is this different from the sorting approach?

Sorting the array first places consecutive numbers next to each other, so a single scan finds the longest run. But sorting is O(n log n), which violates the linear-time constraint. The HashSet approach avoids sorting entirely and achieves O(n) at the cost of O(n) extra space.

| Approach | Time | Space | Notes |
|---|---|---|---|
| HashSet + expand | O(n) | O(n) | Linear, no sorting |
| Sort + scan | O(n log n) | O(1) or O(n) | Depends on sort |

// Sorting approach: O(n log n)
Arrays.sort(serials);
int maxLen = 1, curLen = 1;
for (int i = 1; i < serials.length; i++) {
    if (serials[i] == serials[i - 1] + 1) curLen++;
    else if (serials[i] != serials[i - 1]) curLen = 1;
    maxLen = Math.max(maxLen, curLen);
}

What about deduplication?

The HashSet automatically removes duplicates when numbers are added. This means repeated values do not inflate the run length and do not cause extra inner-loop iterations. The expansion naturally counts each distinct consecutive value once.

int[] serials = {1, 2, 2, 3, 3, 3, 4};
// Set: {1, 2, 3, 4}
// Longest consecutive: 4

What are edge cases?

Edge cases include an empty array (return 0), a single element (return 1), all elements the same (return 1), and elements spread far apart with no consecutive pair (return 1).

longestConsecutive(new int[]{});          // 0
longestConsecutive(new int[]{42});        // 1
longestConsecutive(new int[]{5, 5, 5});   // 1
longestConsecutive(new int[]{10, 100});   // 1

What are common mistakes?

The most common mistake is not using the start-only guard, which makes the algorithm scan forward from every number, turning it into O(n squared) in the worst case. Another mistake is iterating over the original array instead of the set, which processes duplicate values multiple times.

// Wrong: no start guard, scans from every number (O(n^2))
for (int num : set) {
    int current = num;
    int length = 1;
    while (set.contains(current + 1)) { current++; length++; }
    maxLength = Math.max(maxLength, length);
}

// Correct: start guard makes it O(n)
for (int num : set) {
    if (!set.contains(num - 1)) { // <-- the guard
        int current = num;
        int length = 1;
        while (set.contains(current + 1)) { current++; length++; }
        maxLength = Math.max(maxLength, length);
    }
}

What should a senior engineer know?

A senior engineer explains the amortised O(n) analysis in detail, not just claims it. They mention that the start-only guard is the key insight, that iterating over the set (not the array) avoids duplicate processing, and that the HashSet deduplicates automatically. They also know this problem is a classic example of trading space for time to beat the O(n log n) sorting baseline.