03
Set membership tricks (Arrays & Hashing Sub-pattern)
Put everything into a set first; then each "is X present?" question is O(1). The trick is choosing where to start so nothing is walked twice.
Signals in the problem statement
- ›
"contains duplicate"
- ›
"longest consecutive sequence" in O(N)
- ›
"smallest missing positive"
- ›
values matter, positions don't
What makes it different
No pairing, no grouping — just presence. When the problem forbids extra space, the array itself can act as the set (place value v at index v − 1).
Questions
ordered from “learn the idea” to “recognise it without help”- 1Contains DuplicateWalkthroughEasyBasic Anchor·LeetCode #217
- 2Longest Consecutive SequenceWalkthroughMediumMedium·LeetCode #128
- 3First Missing PositiveWalkthroughHardTricky / Edge Case·LeetCode #41
Template
set-run-template.cpp
// Longest run of consecutive values (any order in the array).
int longestRun(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int best = 0;
for (int x : s) {
if (s.count(x - 1)) continue; // not the start of a run: someone else will count it
int length = 1;
while (s.count(x + length)) length++;
best = max(best, length);
}
return best;
}Remember this · Arrays & Hashing
Trigger
"Have I seen X before?", pairs that add up to a target, grouping things that look alike, counting occurrences.
Think
Instead of scanning again for each element, can I remember earlier elements in a map?
Key question
What exactly do I store as the key, and what as the value?