Sets & Maps

Sets & Maps help you trade space for time.

Key Ideas

• Set: fast membership checks (x in set) and de-duplication.
• Map: fast key-to-value lookup (counts, indices, grouping).
• Many problems become one-pass solutions by storing previously seen information.

COMMON BUGS AND MISCONCEPTIONS

Even if you understand the theory, there are a few "gotchas" that trip people up:

1. Iteration order may not be deterministic: The order in which you iterate over a set/map is usually not the insertion order (unless using specific ordered structures like Java's LinkedHashMap). It depends on hashing and may change between runs. Don't rely on it.
2. Cannot update while iterating: Modifying a set/map (adding/removing elements) while iterating through it often causes runtime errors.
   • Workaround: Collect keys to remove in a separate list, then iterate that list to remove from the map.
3. Keys must be immutable: In languages like Python, you cannot use a mutable list as a key.
   • Fix: Convert lists to tuples (tuple(arr)) or strings (",".join(arr)) before using them as keys.

KEY TAKEAWAYS

• Complexity: Basic operations are generally $O(1)$.
• Applications:
  • Linear Scan Tradeoff: Trade $O(1)$ space for $O(n)$ space to get $O(1)$ lookups.
  • Frequency Maps: Counting occurrences of elements.
• Triggers:
  • There is a "key-like" concept.
  • Input/output order is irrelevant.
  • Multiple linear scans or finding duplicates/common elements.
• Keywords: frequency, unique, duplicate, grouping, union, intersection, anagram, caching.