Longest Consecutive Sequence

Medium#128a set of numbers

You get an unsorted array of numbers. Find the length of the longest chain of numbers that follow each other, x, x + 1, x + 2 and so on; where they stand in the array does not matter. Our example: [20, 4, 21, 2, 1, 3, 15] — the answer is 4: 1, 2, 3, 4.

128 Longest Consecutive SequenceWalkthrough · 1×

Example: [20, 4, 21, 2, 1, 3, 15]. Below the array is the set, drawn in order so that a chain stands side by side.

02014221324153615numbers1234152021
current numbercounted in the chainx − 1 is therethe longest chain

Put every number into a set: now "is it there?" takes one step

01/38
restart · back · play · step
Speed
1function longestConsecutive(nums):
2 numbers = set of nums
3 best = 0
4 for each x in nums:
5 if x - 1 in numbers:
6 continue
7 length = 1
8 while x + length in numbers:
9 length = length + 1
10 best = max(best, length)
11 return best
state
numbers
{20, 4, 21, 2, 1, 3, 15}
best
–
x
–
length
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every chain has one start: the number with no x − 1 in the set. A number with x − 1 there sits inside someone else's chain, so it is skipped at once.
  2. From a start the chain is counted upwards, x + 1, x + 2, while the set has the next number. The set answers each of these questions in one step.
  3. So each number is stepped on at most once inside a chain, and the loop inside the loop still makes O(n) steps in total.

Complexity

Time O(n): set lookups are O(1) on average, and each number is counted in at most one chain. Sorting first would take O(n log n). Memory O(n) for the set.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.