Longest Consecutive Sequence DSA Solution - Study Chapter | QuizMaker

Longest Consecutive Sequence explained with sorting brute force, optimized hash set starts, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 9: Hashing & Prefix Sum

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.

Input	Output	Why
`nums = [100,4,200,1,3,2]`	`4`	The longest consecutive run is 1,2,3,4.

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

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> seen(nums.begin(), nums.end());
        int best = 0;

        for (int x : seen) {
            if (!seen.count(x - 1)) {
                int length = 1;
                while (seen.count(x + length)) length++;
                best = max(best, length);
            }
        }

        return best;
    }
};

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) seen.add(x);

        int best = 0;
        for (int x : seen) {
            if (!seen.contains(x - 1)) {
                int length = 1;
                while (seen.contains(x + length)) length++;
                best = Math.max(best, length);
            }
        }

        return best;
    }
}

Sample Dry Run

Step	State	Result
Build set	{100,4,200,1,3,2}	Lookups are O(1) average
x = 1	0 is absent	Start sequence
Expand	2,3,4 exist	length = 4
Other numbers	2,3,4 are skipped as starts	answer = 4

Complexity

Measure	Value	Reason
Time	O(n)	Each number is inserted once and expanded only from true sequence starts.
Space	O(n)	The hash set stores unique numbers.

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

Why only expand from sequence starts?

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

Why does this stay O(n)?

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

What is the core pattern?

Hash set lookup with sequence-start detection.