Skip to content

Set Interface

Operations Syntax What does it do
Container build(A) given an iterable A, build sequence fro items in A
Container len(A) return the number of stored items
Static find(k) return the stored item with key k
Dynamic insert(x) add x to set (replace item with key x.key if one already exists)
Dynamic delete(x) remove and return the stored item with key k
Order iter_ord() return the stored items one-by-one in key order
Order find_min() return the stored items with smallest key
Order find_max() return the stored items with largest key
Order find_next(k) return the stored items with smallest key larger than k
Order find_prev(k) return the stored items with largest key smaller than k

Set Implementations and Operations Cost

Data Structure Build Search Insert/Delete find_min() find_prev(k)
Array \(O(n)\) \(O(n)\) \(O(n)\) \(O(n)\) \(O(n)\)
Sorted Array \(O(n\log n)\) \(O(\log n)\) \(O(n)\) \(O(1)\) \(O(\log n)\)
Hash Table/Set \(O(n)\) \(O(1)\) \(O(1)\) \(O(n)\) N/A
Binary Search Tree \(O(n\log n)\) \(O(\log n)\) \(O(\log n)\) \(O(\log n)\) \(O(\log n)\)

An unordered array would be more than a reasonable way to implement this set interface and would have a linear search time.

Python Sets Overview

A set in Python is an unordered collection of unique objects, ensuring the absence of duplicate values. Furthermore, it allows us to perform several operations on such collections, such as intersection (identifying common elements), union (combining all unique elements), and difference (detecting unique items in a set).

Key Characteristics

  • Unordered: Elements are not stored in any specific order
  • Unique: No duplicate elements allowed
  • Mutable: Can add or remove elements
  • Hashable: Elements must be hashable (immutable)

Basic Operations

Creating Sets

# Empty set
empty_set = set()

# Set from list
numbers = set([1, 2, 3, 4, 5])

# Set literal
fruits = {'apple', 'banana', 'orange'}

# Set from string (creates set of characters)
char_set = set('hello')  # {'h', 'e', 'l', 'o'}

Adding Elements

my_set = set()
my_set.add(1)           # Add single element
my_set.update([2, 3, 4]) # Add multiple elements

Removing Elements

my_set = {1, 2, 3, 4, 5}
my_set.remove(3)        # Raises KeyError if element doesn't exist
my_set.discard(6)       # No error if element doesn't exist
popped = my_set.pop()   # Remove and return arbitrary element
my_set.clear()          # Remove all elements

Set Operations

Mathematical Operations

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}

# Union
union = set1 | set2  # or set1.union(set2)
# Result: {1, 2, 3, 4, 5, 6}

# Intersection
intersection = set1 & set2  # or set1.intersection(set2)
# Result: {3, 4}

# Difference
difference = set1 - set2  # or set1.difference(set2)
# Result: {1, 2}

# Symmetric Difference
symmetric_diff = set1 ^ set2  # or set1.symmetric_difference(set2)
# Result: {1, 2, 5, 6}

Membership Testing

my_set = {1, 2, 3, 4, 5}
print(3 in my_set)      # True
print(6 not in my_set)  # True

Common Use Cases

  1. Removing Duplicates: Convert list to set and back
  2. Finding Unique Elements: Set operations for uniqueness
  3. Membership Testing: Fast O(1) lookups
  4. Mathematical Operations: Union, intersection, difference

Time Complexity

  • Add/Remove: O(1) average case
  • Membership: O(1) average case
  • Union/Intersection: O(len(s1) + len(s2))
  • Iteration: O(n)