Longest Consecutive Sequence: The Hash Set Trick Interviewers Want to See
3 views
"Given an unsorted array of integers, return the length of the longest run of consecutive values." For example, in [100, 4, 200, 1, 3, 2] the answer is 4, because 1, 2, 3 and 4 are all present. The question looks simple, but it is a favourite in phone screens because the obvious approach and the optimal approach are different, and the interviewer wants to watch you get from one to the other.
Start with the honest baseline
Say the simple idea out loud first: sort the array, then walk through it counting runs. Equal neighbours are skipped, a neighbour exactly one larger extends the run, and anything else resets the counter. This runs in O(n log n) time and is easy to get right. Many interviewers will then ask, "Can you do it in linear time?" That is your cue for the real solution.
The O(n) idea: only start counting at the beginning of a run
Put every number into a hash set. Then, for each number x in the set, ask one question: is x - 1 in the set? If it is, x is not the start of a sequence, so skip it. If it is not, x starts a run, so count upward: x + 1, x + 2, and so on, while those values exist. Track the best length you see.
The key insight to explain is why this is linear even though there is a loop inside a loop. Each number is visited by the inner while loop at most once, because we only begin counting from run starts, and every number belongs to exactly one run. The total work across all inner loops is therefore O(n), plus O(n) for building the set.
A clean Python version
def longest_consecutive(nums):
s = set(nums)
best = 0
for x in s:
if x - 1 not in s:
y = x
while y + 1 in s:
y += 1
best = max(best, y - x + 1)
return best
Notice that the outer loop goes over the set, not the original list. That matters when the input has many duplicates, for example a million copies of the same value. Iterating over the list would repeat the x - 1 check needlessly. It is a small detail, and mentioning it shows care.
Edge cases worth testing aloud
An empty array should return 0. A single element returns 1. Duplicates such as [1, 2, 2, 3] should return 3, not 4. Negative numbers and zero work without special handling, and so do very large values, because we never allocate an array indexed by value. If you are using a language with fixed-size integers, mention that x + 1 could overflow at the maximum integer, and guard against it.
Follow-ups you might get
Interviewers sometimes ask you to return the sequence itself rather than its length. Store the start and best length and rebuild the range at the end. Another common follow-up is the streaming version, where numbers arrive one at a time and you must report the current longest run. That leads naturally to union-find or to a hash map that stores run boundaries: when x arrives, look up the run ending at x - 1 and the run starting at x + 1, merge them, and update only the two endpoints. Describing the endpoint-map approach clearly, even without coding it fully, usually earns strong marks.
How to present it in the interview
Spend the first minute restating the problem and confirming whether duplicates and negatives are allowed. Give the sorting solution and its complexity in one or two sentences, then propose the hash set improvement and explain the "only start at run beginnings" rule before writing code. After coding, trace through the example input by hand. The trace is where many candidates catch an off-by-one in the length calculation.
Practising this under realistic pressure helps more than reading another solution. Some candidates also use Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, so a blank moment on a question like this does not derail the whole round.