Longest Consecutive Sequence

LeetCode 128. Find the length of the longest consecutive-integer subsequence in an unsorted array. The trick is the O(n) hashset solution that only expands from sequence-starts. Requirements Input: unsorted integer array nums. Output: length of the longest run of consecutive integers (order in the array does not matter). O(n) solution: put every element in a hashset; for each element x, only start expanding if x - 1 is NOT in the set (i.e. x is the start of its run). Examples [100, 4, 200, 1, 3, 2] → 4 (the run 1,2,3,4). [0,3,7,2,5,8,4,6,0,1] → 9. [] → 0. Notes O(n log n) sort + scan is acceptable but the interviewer almost always asks for O(n). The "only expand from a start" trick is the key insight; without it the naive expand is O(n²) in the worst case. Common bug: forgetting to dedupe (the hashset does this naturally). Preparation Write the O(n) hashset solution in under 8 min. Be ready to walk through why the inner while-loop is amortized O(1) per element. Follow-up to expect: "what if we need the actual sequence, not just length" → track the start element of the best run.