Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Medium

Longest Consecutive Sequence

Longest Consecutive Sequence in O(n) explained: put values in a hash set and only count upward from run starts, with tested Python code and a live visual.

Also searched as: longest consecutive elements sequence O(n) · longest run of consecutive integers

#️⃣

Try it live Free

Hash Tables

Insert keys into the hash table and see that checking whether a key exists costs O(1). This problem asks "is x - 1 here?" and "is x + 1 here?" over and over, which is only fast because of that.

Open the playground →

The problem

Given an unsorted list of integers, return the length of the longest run of values that form consecutive integers (like 4, 5, 6, 7). The values may appear anywhere in the list, and the target is O(n) time.

Inputnums = [100, 4, 200, 1, 3, 2]
Output4

The run is 1, 2, 3, 4.

Inputnums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output9

0 through 8; duplicates do not extend a run.

The key insight

Put every value in a hash set. A number x is the start of a run only if x - 1 is not in the set. Count upward only from starts, so each value is visited by at most one counting loop and the total work stays linear.

Brute force first: Sorting and scanning for runs takes O(n log n); counting upward from every element without the start check can degrade to O(n²).

Step-by-step approach

  1. Build s = set(nums) to remove duplicates and allow O(1) lookups.
  2. For each x in the set, skip it if x - 1 is in the set (it is not a run start).
  3. Otherwise walk x, x+1, x+2, ... while the next value is in the set, counting the length.
  4. Keep the maximum length seen and return it (0 for an empty list).

Python solution

PYTHON 3tested
def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue               # not the start of a run
        y = x
        while y + 1 in s:
            y += 1
        best = max(best, y - x + 1)
    return best

Complexity

TimeO(n)
SpaceO(n)

The inner while loop only runs from run starts, so across the whole algorithm each value is stepped over at most once. Set lookups are O(1) on average.

Common mistakes

Frequently asked questions

What is the time and space complexity of Longest Consecutive Sequence?

The hash set solution is O(n) time and O(n) space. Sorting first gives O(n log n) time with O(1) extra space if sorting in place is allowed.

Why is the nested while loop still O(n)?

It only starts from values whose predecessor is missing, so each value is part of exactly one walk. The total number of while-loop steps across all starts is at most n.

Can union-find solve this?

Yes, you can union x with x + 1 whenever both exist and track component sizes. It works but is longer than the set solution.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.