DSA Tracker

Visualize

Longest Consecutive Sequence

Hash set, count only from a run's head

time O(n)space O(n)

Consecutive means consecutive in VALUE, not in position, so the cells of a run are scattered anywhere across the array — which is why sorting is the obvious answer and why it costs O(n log n). Put every value in a hash set instead and 'is v + 1 present?' becomes an O(1) question, so a run can be walked directly. Walking from every value would still be quadratic on a long run, because each of its members would re-walk the whole tail. The fix is one test: only start walking at a value whose predecessor v - 1 is absent, meaning it is the head of its run. Every value is then walked exactly once, by its own head, and the total is linear. Duplicates need no special handling; the set already collapsed them.

Details

Animated on: nums = [100, 4, 200, 1, 3, 2, 4, 5]. Find the length of the longest run of consecutive integers, in any order and ignoring duplicates. Answer: 5 (the values [1, 2, 3, 4, 5]).

Problem:Longest Consecutive SequenceMedium

Pattern:Hashing and Frequency Maps

Hash set, count only from a run's head

step 1 / 15

100
[0]
4
[1]
200
[2]
1
[3]
3
[4]
2
[5]
4
[6]
5
[7]

Sorting these 8 numbers would find the runs in O(n log n). Instead every value goes into a set first — 7 distinct values out of 8 cells, so the duplicate 4 collapses away — and membership becomes an O(1) question. The whole trick is asking that question about v - 1.

Pseudocode
1FUNCTION longestConsecutive(nums)
2  seen <- SET OF nums
3  best <- 0
4  FOR EACH v IN nums
5    IF v - 1 IN seen
6      CONTINUE
7    length <- 1
8    WHILE v + length IN seen
9      length <- length + 1
10    best <- MAX(best, length)
11  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. Sorting these 8 numbers would find the runs in O(n log n). Instead every value goes into a set first — 7 distinct values out of 8 cells, so the duplicate 4 collapses away — and membership becomes an O(1) question. The whole trick is asking that question about v - 1.
  2. nums[0]=100 is a run head — 99 is not in the set — but 101 is missing too, so it is a run of one and the walk stops immediately. Best is now 1 — the first run measured. An isolated value costs a single set lookup; it is not what makes this scan expensive.
  3. nums[1]=4 is SKIPPED without counting anything, because 3 is also in the set — so 4 sits in the middle of a run, not at its head. Whichever value does start that run will walk through 4 anyway. This one test is what keeps the total work linear: every value is walked exactly once, by its own run's head.
  4. nums[2]=200 is a run head — 199 is not in the set — but 201 is missing too, so it is a run of one and the walk stops immediately. Best is now 1, still held by [100]. An isolated value costs a single set lookup; it is not what makes this scan expensive.
  5. nums[3]=1 IS a run head: 0 is not in the set, so nothing can extend it downward. Start counting up from here with length 1.
  6. 2 is in the set, so the run starting at 1 stretches to [1, 2] — length 2. Note the walk jumps to index 5, nowhere near index 3: consecutive VALUES do not have to be neighbouring cells, which is exactly why scanning positions cannot find them.
  7. 3 is in the set, so the run starting at 1 stretches to [1, 2, 3] — length 3. Note the walk jumps to index 4, nowhere near index 3: consecutive VALUES do not have to be neighbouring cells, which is exactly why scanning positions cannot find them.
  8. 4 is in the set, so the run starting at 1 stretches to [1, 2, 3, 4] — length 4. Note the walk jumps to index 1, nowhere near index 3: consecutive VALUES do not have to be neighbouring cells, which is exactly why scanning positions cannot find them.
  9. 5 is in the set, so the run starting at 1 stretches to [1, 2, 3, 4, 5] — length 5. Note the walk jumps to index 7, nowhere near index 3: consecutive VALUES do not have to be neighbouring cells, which is exactly why scanning positions cannot find them.
  10. 6 is missing, so the run ends at [1, 2, 3, 4, 5]. Its length 5 beats the previous best, so best <- 5.
  11. nums[4]=3 is SKIPPED without counting anything, because 2 is also in the set — so 3 sits in the middle of a run, not at its head. Whichever value does start that run will walk through 3 anyway. This one test is what keeps the total work linear: every value is walked exactly once, by its own run's head.
  12. nums[5]=2 is SKIPPED without counting anything, because 1 is also in the set — so 2 sits in the middle of a run, not at its head. Whichever value does start that run will walk through 2 anyway. This one test is what keeps the total work linear: every value is walked exactly once, by its own run's head.
  13. nums[6]=4 is SKIPPED without counting anything, because 3 is also in the set — so 4 sits in the middle of a run, not at its head. Whichever value does start that run will walk through 4 anyway. This one test is what keeps the total work linear: every value is walked exactly once, by its own run's head.
  14. nums[7]=5 is SKIPPED without counting anything, because 4 is also in the set — so 5 sits in the middle of a run, not at its head. Whichever value does start that run will walk through 5 anyway. This one test is what keeps the total work linear: every value is walked exactly once, by its own run's head.
  15. Every cell has been visited once by the outer loop and at most once more by a run walk, so the answer is 5 — the values [1, 2, 3, 4, 5] — in O(n) time, paid for with the O(n) set. Sorting would have given the same answer more slowly.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Consecutive Sequence in the editorAll Arrays problemsBack to roadmap