Overview

Problems about scanning a list or string once and remembering what you've seen. Often the answer is "trade memory for a faster lookup".

When to Use it

• "Does X appear / appear twice / how many times?" → hash set or counter.
• A nested loop comparing every pair → replace the inner loop with a lookup.
• Output size is a fixed multiple of the input → pre-allocate.

Templates

# seen set: first repeat wins
seen = set()
for n in nums:
    if n in seen:
        return True
    seen.add(n)

# adjacent pairs
for i in range(len(s) - 1):
    ...  # s[i], s[i + 1]

# pre-allocate, write by index
result = [0] * (2 * len(nums))

Problems

Related: LeetCode