Maps and Sets

Introduction to Maps

A map (called dict in Python) stores key → value pairs.

Tutorial

age = {
    "Alice": 12,
    "Bob": 14
}

Here: Keys: "Alice", "Bob" and Values: 12, 14

Why maps are useful

• Fast lookup → O(1) average time
• Counting frequencies
• Grouping values
• Tracking visited elements
• Storing indices
• Caching results

Basic Usage

d = {}

# Insert / Update (Fast O(1))
d["apple"] = 3

# Read (Fast O(1))
x = d["apple"]

# Check existence (Fast O(1))
if "apple" in d:
    print("exists")

# Safe get with default (returns 0 if "banana" doesn't exist in d)
count = d.get("banana", 0)

# Safe get with default (returns an empty string "" if "banana" doesn't exist in d)
x = d.get("banana", "")

# Safe get with default (returns an empty list [] if "banana" doesn't exist in d)
y = d.get("banana", [])

# Loop over keys
for key in d:
  print(key, d[key])
    
# Loop over key, value pairs
for key, value in d.items():
  print(key, value)

Introduction to Sets

A set stores unique values only.

Tutorial

s = {1, 1, 2, 2, 3}
# result -> {1,2,3}

Why sets are useful

• Remove duplicates
• Very fast membership check → O(1)
• Intersection / union / difference operations
• Detect duplicates
• Track visited elements

Basic Usage

s = set()

# Add (Fast O(1))
s.add(5)

# Remove (Fast O(1))
s.remove(5)

# Membership test (Fast O(1))
if 5 in s:
    print("exists")

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

# Union
a | b # {1, 2, 3, 4, 5}

# Intersection
a & b # {3}

# Difference
a - b # {1, 2}
b - a # {4, 5}
a - (a & b) # {1, 2}

Problems

1. Unique Count

Given an array nums of integers, print the number of unique integers.

nums = [1, 2, 2, 3, 3, 3, 4]
Output: 4

Solution

nums = [1, 2, 2, 3, 3, 3, 4]

# Create an empty dictionary to track seen numbers
seen = {}

# Loop through each number
for value in nums:
    # Mark the number as seen by putting it in the dictionary
    seen[value] = True

# Number of unique elements is the size of the dictionary
print(len(seen))

2. Count Frequencies

Given an array nums, count how many times each number appears.

nums = [1,1,2,2,2,3]
Output: {1:2, 2:3, 3:1}

Solution

nums = [1, 1, 2, 2, 2, 3]

frequency = {}

for value in nums:
    # If number already exists, increase its count
    if value in frequency:
        frequency[value] += 1
    else:
        # Otherwise initialize with count 1
        frequency[value] = 1

print(frequency)

3. Most Frequent Number

Return the number that appears most frequently.

nums = [1,1,2,2,2,3]
Output: 2

Solution

nums = [1, 1, 2, 2, 2, 3]

frequency = {}

for value in nums:
    frequency[value] = frequency.get(value, 0) + 1

most_common = None
max_count = 0

for key in frequency:
    if frequency[key] > max_count:
        max_count = frequency[key]
        most_common = key

print(most_common)

4. First Non-Repeating Number

Return the first number that appears only once.

nums = [4,1,2,1,2,3]
Output: 4

Solution

nums = [4, 1, 2, 1, 2, 3]

frequency = {}

for value in nums:
    frequency[value] = frequency.get(value, 0) + 1

# Second pass: find first with frequency 1
for value in nums:
    if frequency[value] == 1:
        print(value)
        break

5. Check If Two Arrays Are Anagrams

Two arrays are anagrams if they contain same elements with same frequency.

a = [1,2,3]
b = [3,2,1]
Output: True

Solution

a = [1, 2, 3]
b = [3, 2, 1]

freq_a = {}
freq_b = {}

for x in a:
    freq_a[x] = freq_a.get(x, 0) + 1

for x in b:
    freq_b[x] = freq_b.get(x, 0) + 1

print(freq_a == freq_b)

6. Index Mapping (Value → Indices)

Store indices for each number. (Where are the 1s, where are the 2s, ...?)

nums = [1,2,1,2,1]
Output: {1:[0,2,4], 2:[1,3]}

Solution

nums = [1, 2, 1, 2, 1]

indices = {}

for i in range(len(nums)):
    value = nums[i]

    if value not in indices:
        indices[value] = []

    indices[value].append(i)

print(indices)

7. Two Sum (Classic LeetCode)

Return indices of two numbers that add to target.

nums = [2,7,11,15], target=9
Output: [0,1]

Solution

nums = [2, 7, 11, 15]
target = 9

lookup = {}

for i in range(len(nums)):
    needed = target - nums[i]

    if needed in lookup:
        print([lookup[needed], i])
        break

    lookup[nums[i]] = i

8. Count Distinct Pairs

Count unique pairs (a,b) such that a+b = k.

nums = [1,2,3,4,5], k = 6
Output: 2 # 1+5=6, 2+4=6

Solution

nums = [1,2,3,4,5]
k = 6

seen = {}
count = 0

for x in nums:
    if k - x in seen:
        count += 1
    seen[x] = True

print(count)

9. Group Words by Length

words = ["cat", "dog", "orange", "bat", "banana"]
Output: {3: ["cat", "dog", "bat"], 6:["orange", "banana"]}

Solution

words = ["cat", "dog", "orange", "bat", "banana"]

groups = {}

for word in words:
    length = len(word)

    if length not in groups:
        groups[length] = []

    groups[length].append(word)

print(groups)