Longest Consecutive Sequence – Solution & Complexity

• Find the length of the longest run of consecutive integers present in nums (order in the array doesn't matter, only which values exist).
• The obvious approach — sort, then scan for runs — works and is easy to explain, but costs O(n log n).
• The problem explicitly asks for O(n), which rules out sorting and requires a hash-set-based approach instead.

• Put every number into a hash set for O(1) membership checks.
• For each number x in the set, only try to extend a sequence starting at x if x - 1 is not in the set — that means x is the smallest element of its consecutive run, so it's a valid starting point.
• This guarantees each run is only walked once (from its start), not once per element in it, which is what keeps the overall algorithm O(n) despite the inner while loop.

• From a valid start x, keep checking x + 1, x + 2, ... as long as they're in the set, counting the run's length.
• Track the maximum run length seen across all valid starting points.
• Because every element is visited at most twice total (once as a candidate start check, once while extending a run it belongs to), the total work across all iterations stays linear.

O(n) time (each element examined a constant number of times) and O(n) space for the hash set — meets the problem's stated time complexity requirement.

• Forgetting the x - 1 not in num_set guard and extending from every element — still produces the correct answer, but degrades to O(n^2) worst case (e.g. one big consecutive run) since every element re-walks the whole run.
• Using a sorted approach when O(n) is explicitly required — mention the tradeoff even if you start there, then optimize to the hash-set version.
• Follow-ups: how would you also return the actual sequence, not just its length? How does the approach change if duplicates should count once (the hash set already handles this for free)?