The tell: Consecutive run in an unsorted array, with sorting explicitly ruled out by an O(n) requirement.
How you get there
1Put everything in a set so membership is O(1).
2Only start counting at x when x-1 is absent — that makes x the head of its run.
3Each run is therefore walked exactly once, so the nested loop is O(n) in total, not O(n²).
Solution
Python
def longest_consecutive(nums: list[int]) -> int:
values = set(nums)
best = 0
for x in values:
if x - 1 in values:
continue # not the start of a run; skip
length = 1
while x + length in values:
length += 1
best = max(best, length)
return best
Time
O(n)
Space
O(n)
What goes wrong
Dropping the `x - 1 in values` guard makes each run rewalked from every member, giving O(n²).