Sets

Sets

# Unordered collection of unique elements
# Add/remove/lookup: O(1) average

S = set()
S.add(1)         # O(1)
S.remove(1)      # O(1), KeyError if absent
S.discard(99)    # O(1), no error if absent
1 in S           # O(1)

# Set operations
A = {1,2,3,4}
B = {3,4,5,6}
A | B   # union:        {1,2,3,4,5,6}
A & B   # intersection: {3,4}
A - B   # difference:   {1,2}
A ^ B   # symmetric diff: {1,2,5,6}

# Common pattern: visited set in BFS/DFS
def bfs(graph, start):
    visited = {start}   # O(1) lookup
    queue   = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in visited:  # O(1)
                visited.add(nb)
                queue.append(nb)

# Deduplicate while preserving order
list(dict.fromkeys([1,2,2,3,1,4]))  # [1,2,3,4]