4. Tuples & Sets

💡 Why this matters for DSA Sets give you O(1) lookup — essential for duplicates, intersection, and membership problems. Tuples are your go-to for hashable keys in dictionaries.

4.1 Tuples (immutable lists)

python

t = (1, 2, 3)
t[0]        # 1
t[1:3]      # (2, 3)

# t[0] = 99   ❌ Error — tuples are immutable

When to use tuples

Use case	Example
Dictionary key	`cache[(x, y)] = result`
Returning multiple values	`return (min_val, max_val)`
Fixed data (coordinates)	`points = [(1,2), (3,4)]`

python

# Tuple unpacking
a, b = (5, 10)       # a=5, b=10
x, y = point

# Swap (uses tuple packing/unpacking)
a, b = b, a

# Single element tuple (note the comma)
single = (5,)        # Without comma: just int 5

✅ Tip — Tuples vs Lists quick decision:

Will it change? → List

Used as dict key? → Tuple

Coordinates / fixed pair? → Tuple

4.2 Sets (unique elements, O(1) lookup)

python

s = {1, 2, 3, 3, 3}
print(s)             # {1, 2, 3}  (duplicates auto-removed)

# Creating sets
empty_set = set()             # ❌ {} creates an empty dict!
arr_to_set = set([1, 2, 2, 3])  # {1, 2, 3}

# Core operations
s.add(4)             # {1, 2, 3, 4}    O(1)
s.remove(2)          # {1, 3, 4}       O(1) (raises error if missing)
s.discard(99)        # {1, 3, 4}       O(1) (no error if missing)
x in s               # True / False    O(1) ⭐
len(s)               # 3               O(1)

⚠️ Warning: Set elements must be hashable Lists and dicts can't go inside sets. Tuples can.
python
bad = {[1, 2]}   # ❌ TypeError
good = {(1, 2)}  # ✅

4.3 Set Operations

python

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

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

a.union(b)
a.intersection(b)
a.difference(b)

Common DSA patterns with sets

python

# 1. Remove duplicates from list
arr = [1, 2, 2, 3, 1, 4]
unique = list(set(arr))           # Order NOT preserved

# 2. Find duplicates
seen = set()
for x in arr:
    if x in seen:
        print(f"Duplicate: {x}")
    seen.add(x)

# 3. Check if two arrays have common element
set_a = set(arr1)
common = any(x in set_a for x in arr2)  # O(n + m)

# 4. Missing number (0..n)
nums = [3, 0, 1]
n = len(nums)
missing = (set(range(n + 1)) - set(nums)).pop()

✅ Tip: Set membership is O(1) vs list O(n) For large data, always convert to set if you only need lookups.
python
# ❌ Slow for large lists
if x in huge_list:   # O(n)

# ✅ Fast
if x in set(huge_list):  # O(1)

Practice Drill

python

# 1. Find common elements between two lists
# 2. Find elements in first list but not in second
# 3. Check if a list has all unique elements
# 4. Given a string, find the first non-repeating character

💡 Click for Solutions

python

# 1. Common elements
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]
print(list(set(a) & set(b)))  # [3, 4]

# 2. In first but not second
print(list(set(a) - set(b)))  # [1, 2]

# 3. All unique?
arr = [1, 2, 3, 4, 2]
print(len(arr) == len(set(arr)))  # False

# 4. First non-repeating character
s = "swiss"
for ch in s:
    if s.count(ch) == 1:
        print(ch)  # 'w'
        break

← Lists | Next → Dictionaries