Skip to main content
DSA patterns

Longest Consecutive Sequence

mediumArrays and hashingMetaGoogleMicrosoft

Problem statement

You are given an unsorted array of integers nums. Find the length of the longest run of consecutive integers that all appear somewhere in the array — the values don't need to be next to each other in nums, only consecutive as numbers (like 3, 4, 5), and you must solve it in O(n) time.

This is the same shape as finding the longest unbroken run of consecutive port numbers or sequence IDs scattered across an unordered list — you care about how long the longest unbroken chain is, not where its pieces sit in the original array.

Examples

Example 1

Input: nums = [100,4,200,1,3,2]

Output: 4

Explanation: The longest run of consecutive values is 1, 2, 3, 4 — length 4. 100 and 200 are isolated.

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]

Output: 9

Explanation: Every value from 0 to 8 appears somewhere in the array (0 appears twice), giving a run of length 9.

Example 3

Input: nums = [1,0,1,2]

Output: 3

Explanation: The values 0, 1, 2 form a run of length 3; the repeated 1 doesn't extend it further.

Hints

Hint 1: Sorting would make consecutive values sit next to each other, letting you scan once for the longest run — but sorting costs more than the O(n) the problem asks for. Keep it in your back pocket as a step below the best solution.

Approach

Optimal: Hash set, skip non-starts

Intuition

Put every value into a hash set for O(1) membership checks — that alone would make the brute force's checks fast, but it still repeats work by starting a scan from every value, including values in the middle of a run. The key improvement: only start counting from a value that is genuinely the start of a run — meaning value - 1 is not in the set. Every other value gets skipped as a starting point, because it will already be counted as part of a run that starts earlier. This guarantees each value is visited at most twice in total (once as a possible start, once while extending some run), which is what makes the whole thing O(n).

Steps

  1. Put every value from nums into a hash set numSet (this also removes duplicates for free).
  2. For each value num in numSet: if num - 1 is also in the set, skip it — it's not the start of a run.
  3. Otherwise, num starts a run. Count forward: while num + length is in the set, increment length.
  4. Update longest with length if it's bigger.
  5. Return longest after every value in the set has been checked.

Dry run

nums = [100, 4, 200, 1, 3, 2] → numSet = {100, 4, 200, 1, 3, 2}

num num-1 in set? is a start? run length
100 no yes 1 (101 not in set)
4 yes (3) no —
200 no yes 1 (201 not in set)
1 no yes 4 (2, 3, 4 all in set; 5 is not)
3 yes (2) no —
2 yes (1) no —

Only 100, 200 and 1 are ever treated as starts — the other three are skipped immediately, without re-walking the run they belong to. longest = 4, matching the expected output, with far less repeated work than either earlier approach.

Edge cases: an empty array leaves numSet empty, so the loop never runs and longest stays 0.

Complexity

Time O(n) - building the set is one O(n) pass. In the main loop, most values are skipped in O(1) because they aren't starts.

Space O(n) - the hash set holds up to n distinct values.

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        num_set = set(nums)
        longest = 0
        for num in num_set:
            if (num - 1) not in num_set:
                length = 1
                while (num + length) in num_set:
                    length += 1
                longest = max(longest, length)
        return longest


if __name__ == "__main__":
    print(Solution().longestConsecutive([100, 4, 200, 1, 3, 2]))              # 4
    print(Solution().longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))       # 9
    print(Solution().longestConsecutive([1, 0, 1, 2]))                        # 3
    print(Solution().longestConsecutive([]))                                  # 0
RecapThe whole problem in a few lines, for the night before
  • Spot it: longest run of consecutive numbers in an unsorted array, in O(n)
  • Idea: put all numbers in a set; only start counting from a number whose predecessor (x - 1) is not in the set, then walk upward
  • Cost: O(n) time, O(n) space
  • Trap: starting a count from every number makes it O(n²); skip numbers that are not the start of a run

Interview follow-ups

  • Can you return the actual sequence (the list of values), not just its length?

    Yes — once you find a starting value (num - 1 not in the set) whose run length beats the current best, remember num as the start of the best run instead of only its length. After the loop, rebuild the sequence with a simple loop from that starting value up to start + longest - 1. This adds no real cost: you're already walking that exact range while counting the length, so you can just collect it into a list on the winning run instead of discarding it, still O(n) overall.

  • What if nums is far too large to fit in memory, and you need an approximate answer instead?

    You'd give up an exact hash set and instead process nums in sorted chunks (external sort, or a merge of pre-sorted shards), tracking the current run length as you go and only keeping the boundary values between chunks in memory. This trades the O(n) extra space of a full hash set for streaming through sorted data, at the cost of needing the data sorted first — which is exactly the trade-off the 'sort and scan' approach makes, just applied at a scale where the full array can't sit in memory at once.

Frequently asked questions

Without that check, every value tries to start a scan, even values that sit in the middle of a run — so a run of length k gets walked k separate times (once from each of its values), costing O(k²) total for that run alone. Skipping any value whose predecessor is present means only true starting points ever begin a scan, so each run is walked exactly once, in time proportional to its own length. Summed across all runs, that's O(n) instead of O(n²).

It finds the correct answer, but sorting has a hard floor of O(n log n) — no comparison-based sort can do better in general. The problem explicitly asks for O(n), which the hash-set approach hits because it never compares or orders the values; it only asks 'is this exact value present?', which a hash set answers in O(1) on average.

Spotting the longest unbroken run in an unordered set of values — sequence numbers, port ranges, dates with no gaps — is a natural question when checking for missing entries or contiguous capacity. It's also a clean way to test whether someone reaches past 'sort it' for the truly linear solution once the problem explicitly asks for O(n).