? Nested loops O(n ) — it depends how the data is traversed.

[Sascha]

? LeetCode #128: Longest Consecutive Sequence — From Sorting to HashSet & a Big Realization
This one looked simple.
I read the problem, understood the examples, and thought:
"Alright, sort the array and count consecutive numbers. Easy."
? I sketched out the logic in my notebook and wrote the code.
Submitted it — boom:
Beat over 90% in time and memory.
But I couldn’t stop there. Because I know my solution is O(n log n)

? Enter: The Discussion Section
I saw people talking about a HashSet-based O(n) solution.
Wait, O(n)? Without sorting?
That grabbed my attention. I didn’t know much about unordered_set internals, so I dug in.

Saw how using a HashSet could eliminate the need for sorting entirely.
Understood how it could help track sequences more efficiently — by checking only where a sequence starts.

? Mind-Blown Moment
Then I saw a solution with two loops… yet it still claimed to be O(n).
At first, that didn’t make sense. But then I realized:
The inner loop only runs once per unique number — never repeats work.
So overall time complexity remains linear. Elegant!

? Key Takeaways
? Don’t skip the Discussions tab — it’ll challenge your assumptions.
? Understanding HashSet behavior unlocks powerful optimizations.
Writing logic by hand helps internalize edge cases and control flow.
? Nested loops ≠ O(n²) — it depends how the data is traversed.

Источник:

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.