Given an unsorted array, find the length of the longest run of consecutive numbers. It must run in O of n time, so no sorting.
DSA Animator › DSA Revision › Arrays › Longest Consecutive Sequence
Remember: only count from the start of a run, where x minus 1 is missing. That keeps the whole thing linear. The video solves Longest Consecutive Sequence (LeetCode 128, Medium) with the Hash Set pattern from the Arrays topic, and you can replay every step in the interactive Longest Consecutive Sequence animation.
Given an unsorted array, find the length of the longest run of consecutive numbers. It must run in O of n time, so no sorting.
For 100, 4, 200, 1, 3, 2, the longest run is 1, 2, 3, 4. Its length is 4.
Sorting first costs O of n log n. And counting up from every single number repeats the same work again and again.
Put every number in a hash set. Only start counting from a number that begins a run, meaning the number minus 1 is not in the set. Then count up while the next number exists.
100: 99 is missing, so it starts a run of length 1. 4: 3 exists, so 4 is not a start, and we skip it. 200: 199 is missing, so another run of length 1. 1: 0 is missing, so count up: 2, 3 and 4 all exist. That run has length 4, the new best. 3 and 2 are not starts, so they are skipped. The answer is 4.
In code, add every number to a set. For each number whose predecessor is missing, count up while the next number is in the set, and keep the longest. Each number is visited a constant number of times, so it's O of n time and O of n space.
Remember: only count from the start of a run, where x minus 1 is missing. That keeps the whole thing linear.