Hash Set

Hash Set Code Labs

Mental Model

A set answers whether a distinct hashable value is present. It deliberately stores no attached count, index, or payload. This narrower contract makes intent clearer than a dictionary whose values are meaningless placeholders.

Presence Without Attached Values

Python set supports expected O(1) membership, insertion, and removal under ordinary hashing. Keys must be hashable and keep stable equality/hash behavior while stored. Lists and sets are mutable and cannot be members; use a tuple or frozenset only when that immutable representation matches the problem’s equality rule.

The set documentation(opens in a new tab) defines add, discard, remove, and algebra operations. discard tolerates absence; remove raises KeyError when absence violates the contract.

Track Seen State in One Pass

Test membership before insertion when the output asks whether a value appeared earlier. The invariant is that seen contains exactly the distinct values from the processed prefix. Inserting first would make every current value appear duplicated by itself.

def track_seen_values(values):
    seen = set()
    result = []
    for value in values:
        result.append(value in seen)
        seen.add(value)
    return result

Apply Set Algebra

Intersection expresses “in both,” difference expresses “only on this side,” and union expresses “in either.” These operations return sets and therefore discard duplicates and sequence order. Convert to a sorted list only when the output contract needs deterministic ordering.

def set_relationships(left, right):
    left_set = set(left)
    right_set = set(right)
    return (
        sorted(left_set & right_set),
        sorted(left_set - right_set),
        sorted(left_set | right_set),
    )

Choose set or dict

Use a set for presence, deduplication, visited state, and algebra. Use a dictionary when each key must retain a count, original index, predecessor, or computed value. Use a boolean list when the key domain is small and dense; it may be faster and makes the bounded domain explicit.

Common Pitfalls

• Using a mutable list as a member raises TypeError; choose an immutable semantic key.
• Depending on set iteration order creates unstable output even if one run looks consistent.
• Removing while iterating the same set can raise a runtime error.
• Building set(values) too early loses duplicate positions and encounter order.
• Claiming worst-case O(1) ignores collision behavior and the cost of hashing long keys.

Explain It in an Interview

State exactly what membership means and why no payload is needed. Define when a value enters the set and whether input order must survive. Give expected O(1) operations and O(n) space, while noting that hashing a compound key includes the work needed to hash its contents.

Track Previously Seen Values(opens in a new tab) isolates the prefix invariant. Design HashSet(opens in a new tab) then asks you to implement collision-safe membership without relying on the built-in set.