Longest Consecutive Sequence O(n) Solution: Hash Set Algorithm Explained

The optimal O(n) solution stores all numbers in a hash set, then only expands consecutive sequences from their starting points to achieve linear time complexity.

The Longest Consecutive Sequence problem requires finding the length of the longest streak of consecutive integers in an unsorted array. The kdn251/interviews repository implements this efficient linear‑time algorithm in the LongestConsecutiveSequence class, avoiding the O(n log n) cost of sorting by leveraging constant‑time hash set look‑ups.

How the O(n) Algorithm Works

The solution achieves O(n) time by ensuring each element is processed at most twice: once during set construction and once during sequence expansion.

Step 1: Store Numbers in a Hash Set

First, insert every element from the input array into a HashSet. This provides O(1) average‑time look‑ups and automatically deduplicates the input.

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

Step 2: Identify Sequence Starts

Iterate through each unique number n in the set. A number represents the start of a consecutive sequence only if n - 1 is absent from the set. This check prevents redundant traversal of sub‑sequences.

for (int num : numSet) {
    if (!numSet.contains(num - 1)) {
        // num is the start of a new sequence
    }
}

Step 3: Expand Forward and Count

From each identified start, expand forward by checking n + 1, n + 2, and so on until the next integer is missing. Track the length of each block and update the maximum length found.

int currentNum = num;
int currentStreak = 1;

while (numSet.contains(currentNum + 1)) {
    currentNum += 1;
    currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);

Implementation in kdn251/interviews

According to the source code in the kdn251/interviews repository, the complete implementation resides in leetcode/array/LongestConsecutiveSequence.java. Identical logic also appears in company‑specific folders including company/google/LongestConsecutiveSequence.java and company/facebook/LongestConsecutiveSequence.java.

The longestConsecutive method in the LongestConsecutiveSequence class implements the three‑step hash set approach:

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

public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int longestStreak = 0;
        
        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}

Code Example

Given the input array [100, 4, 200, 1, 3, 2], the algorithm identifies the sequence 1 → 2 → 3 → 4 with length 4:

public class Example {
    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        LongestConsecutiveSequence solver = new LongestConsecutiveSequence();
        int longest = solver.longestConsecutive(nums);
        System.out.println("Longest consecutive length = " + longest); // prints 4
    }
}

The method discovers 1 as a sequence start because 0 is absent from the set, then expands through 2, 3, and 4 before terminating when 5 is not found.

Complexity Analysis

• Time Complexity: O(n) — Each number is added to the set once and visited at most once during the expansion phase. Because the inner while loop only executes for sequence starts, the total work across all iterations remains linear with respect to the input size.
• Space Complexity: O(n) — The hash set stores at most n unique elements from the input array.

Summary

• The O(n) Longest Consecutive Sequence solution uses a hash set to enable constant‑time look‑ups for sequence validation.
• The algorithm only expands sequences from their starting points (where n-1 is missing), ensuring each element is processed at most twice.
• Implementation files in kdn251/interviews include leetcode/array/LongestConsecutiveSequence.java and company‑specific variants for Google and Facebook interview preparation.
• This approach trades O(n) extra space for linear time complexity, outperforming sorting‑based alternatives.

Frequently Asked Questions

Why is the time complexity O(n) rather than O(n²)?

Although the code contains a nested loop structure, the inner while loop only executes when the current number is the start of a sequence. Each number in the set is visited at most once during any expansion phase, so the total number of operations across the entire algorithm remains proportional to the number of elements.

Can this problem be solved without using extra space?

Sorting the array first enables an O(n log n) solution with O(1) auxiliary space (if sorting in‑place). However, achieving true O(n) time complexity requires the hash set approach, which inherently uses O(n) space to store the unique elements for constant‑time look‑ups.

How does the implementation handle duplicate values?

The HashSet automatically deduplicates values during construction. In leetcode/array/LongestConsecutiveSequence.java, the algorithm iterates over the set rather than the original array, so duplicates do not affect sequence counting or degrade the time complexity.

Where can I find alternative implementations in the repository?

The kdn251/interviews repository maintains identical LongestConsecutiveSequence.java implementations across multiple directories. You can find the same O(n) solution in company/google/LongestConsecutiveSequence.java and company/facebook/LongestConsecutiveSequence.java, illustrating how the repository organizes solutions by company interview context.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}