Longest Consecutive Sequence (Set)

To solve the Longest Consecutive Sequence problem within O(n) time, we must avoid sorting, which would take O(n log n). Instead, I recommend using a Hash Set to store all array elements. The core insight is that we only want to start counting a sequence from its smallest number. For any number in the set, if the previous number (num - 1) exists, then this number cannot be the start of a new sequence, so we skip it. If num - 1 is missing, we increment a counter by checking if num + 1, num + 2, etc., exist in the set until the sequence breaks. We track the maximum length found across all such sequences. For example, with input [100, 4, 200, 1, 3, 2], the set contains all these values. When processing 100, 99 is missing, but 101 is not, so the length is 1. When processing 1, 0 is missing, but 2, 3, and 4 are present, giving a sequence length of 4. Crucially, even though we have nested loops, every element is part of exactly one sequence check. Since we only initiate checks from sequence starts, no element is processed more than twice—once when added to the set and once during the inner loop expansion. This ensures linear time complexity. At Uber, where scalability is critical, demonstrating this optimization shows we prioritize efficient algorithms for large-scale data processing rather than settling for acceptable but suboptimal solutions.