Hash based data structures: set, dict, counter - Introduction to Programming - Python

Hash based data structures: set, dict, counter

Fast O(1) membership and lookup using set and dict, plus defaultdict and Counter from collections, with common CP patterns.

`set`

A set is an unordered collection of unique values. Duplicates are automatically discarded.

Creating a Set

Basic Operations

Operation	Method	Complexity
Add	`add(x)`	O(1)
Remove	`remove(x)`	O(1)
Lookup	`x in s`	O(1)
Size	`len(s)`	O(1)

Compare this to a list where x in lst is O(n). For large collections with frequent lookups, a set is dramatically faster.

Sets are Unordered

Elements have no guaranteed order — you cannot access by index:

If you need sorted unique elements, use sorted(s) when iterating:

Set Operations

Sets support mathematical set operations:

Practical Examples

Removing Duplicates from a List

If order matters, use a different approach (as shown in the lists module).

Fast Membership Check

Counting Distinct Elements

`dict`

Up next

Priority Queue: heapq

Min-heap operations using Python's heapq module — push, pop, heapify, the negation trick for max-heap, and practical CP examples.

Feature	`set`	`dict`
Stores	Unique values	Key-value pairs
Lookup	`x in s` — O(1)	`d[key]` — O(1)
Ordered?	No	Insertion order (Python 3.7+)
Sorted?	No	No
Duplicates	Not allowed	Keys must be unique

s = {1, 2, 3}
s = set()               # empty set — note: {} creates an empty dict, not a set!
s = set([1, 2, 2, 3])   # from a list, duplicates removed: {1, 2, 3}
s = set("hello")        # from a string: {'h', 'e', 'l', 'o'}

s = {1, 2, 3}

s.add(4)        # add element: {1, 2, 3, 4}
s.add(2)        # already exists — no change, no error
s.remove(3)     # remove element — raises KeyError if not found
s.discard(99)   # remove if exists — no error if missing
print(len(s))   # 3
print(2 in s)   # True  — O(1)
print(9 in s)   # False — O(1)

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a | b)    # union:               {1, 2, 3, 4, 5, 6}
print(a & b)    # intersection:        {3, 4}
print(a - b)    # difference:          {1, 2}  — in a but not b
print(a ^ b)    # symmetric difference: {1, 2, 5, 6}  — in one but not both

d = {"alice": 95, "bob": 87}

# Access
print(d["alice"])         # 95
print(d.get("alice"))     # 95
print(d.get("xyz"))       # None  — no KeyError
print(d.get("xyz", 0))    # 0     — default value

# Add or update
d["charlie"] = 92
d["alice"] = 100   # overwrites existing value

# Delete
del d["bob"]          # removes key — raises KeyError if missing
d.pop("charlie")      # removes and returns value
d.pop("xyz", None)    # removes if exists, returns None otherwise

# Check existence
print("alice" in d)    # True  — O(1), checks keys only
print(95 in d)         # False — 95 is a value, not a key

print(len(d))          # number of key-value pairs

d = {"alice": 95, "bob": 87, "charlie": 92}

for key in d:                    # iterate over keys
    print(key)

for key, value in d.items():     # iterate over key-value pairs
    print(key, value)

for value in d.values():         # iterate over values
    print(value)

for key in d.keys():             # iterate over keys (explicit)
    print(key)

from collections import Counter

a = [1, 3, 2, 3, 4, 3, 1]
freq = Counter(a)
print(freq)              # Counter({3: 3, 1: 2, 2: 1, 4: 1})
print(freq[3])           # 3
print(freq[99])          # 0  — missing key returns 0, not KeyError

# Most common elements
print(freq.most_common(2))   # [(3, 3), (1, 2)]

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

groups = defaultdict(list)
for x in a:
    groups[x % 3].append(x)   # group by remainder mod 3

for key in sorted(groups):
    print(key, groups[key])

n, s = map(int, input().split())
a = list(map(int, input().split()))

seen = {}
found = False
for i, x in enumerate(a):
    complement = s - x
    if complement in seen:
        print(seen[complement], i)
        found = True
        break
    seen[x] = i

if not found:
    print(-1)

a = list(map(int, input().split()))
b = list(map(int, input().split()))

sa, sb = set(a), set(b)
print(*sorted(sa & sb))   # elements in both
print(*sorted(sa - sb))   # elements in a but not b
print(*sorted(sa | sb))   # all unique elements

memo = {}

def fib(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(50))   # fast — each value computed only once

from collections import defaultdict

n = int(input())
words = [input() for _ in range(n)]

groups = defaultdict(list)
for word in words:
    key = tuple(sorted(word))
    groups[key].append(word)

for group in groups.values():
    print(*group)

Hash based data structures: set, dict, counter

`set`

Creating a Set

Basic Operations

Sets are Unordered

Set Operations

Practical Examples

Removing Duplicates from a List

Fast Membership Check

Counting Distinct Elements

`dict`

Creating a Dict

Basic Operations

Iterating Over a Dict

`defaultdict`

`Counter`

Practical Examples

Frequency Count

Grouping Elements

Two Sum with a Dict

Summary

More CP Patterns

Check if All Elements are Distinct

Count Elements Appearing Exactly Once

Find the First Non-Repeating Character

Intersection and Difference of Two Arrays

Anagram Check

Coordinate Compression

Memoization with a Dict

Counting Pairs with a Given Difference

Tracking Visited States

Grouping Anagrams Together