Pattern visualizer
Find the Longest Consecutive Sequence
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. 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])..
Hash set, count only from a run's head
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.
1FUNCTION longestConsecutive(nums)2 seen <- SET OF nums3 best <- 04 FOR EACH v IN nums5 IF v - 1 IN seen6 CONTINUE7 length <- 18 WHILE v + length IN seen9 length <- length + 110 best <- MAX(best, length)11 RETURN best
← / → step · space play · Home restart