knoopx When to use
Use dict/set (hash table, O(1) avg lookup) for: membership testing, frequency counting, deduplication, grouping by key.
Rules
- Use collections.Counter for frequency counts, defaultdict(list) for grouping
- When you need ordered keys or range queries, use sorted containers or bisect on a sorted list
- For "find if X exists" or "count occurrences," ALWAYS reach for a set or dict first
- NEVER scan a list repeatedly when a set/dict would work
- If the problem involves pairs summing to a target, use a set to check complements in O(n) instead of O(n^2) nested loops
Complexity
Hash table: O(1) avg lookup. Sorted containers: O(log n) lookup.
Example
"Two sum" → store complements in a set: for x in nums: if target - x in seen: return True; seen.add(x). O(n) vs O(n²) nested loops.