Hard · Hash Set
Understand → Visualise → Practice.
The array is unsorted, but set membership can follow consecutive values without sorting. The linear-time trick is to start only where no predecessor exists.
A value begins a sequence only if value − 1 is absent; then count upward while the next value exists.
Duplicates disappear and membership is fast.
Skip values whose predecessor exists.
Count value, value + 1, ... once.
O(n) expected time and O(n) space; every value belongs to one counted run.
Starting a walk from every value makes a long sequence O(n²).
Read the full guide first: Hash Maps and Hash Sets.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.