Set Basics

A hash set (or simply "set") is an unordered collection of unique elements. It uses hashing to provide extremely fast lookups, insertions, and deletions.

Core Operations

• Add: Insert an element - O(1) average
• Remove: Delete an element - O(1) average
• Contains: Check if element exists - O(1) average
• Size: Get number of elements - O(1)

Key Properties

1. No Duplicates: Each element appears at most once
2. Unordered: Elements have no specific order
3. Fast Lookups: O(1) average time to check membership

When to Use Sets

Sets are ideal when you need to:

• Track unique items
• Check for duplicates quickly
• Test membership in O(1) time
• Remove duplicates from a collection
• Perform set operations (union, intersection, difference)

Python Implementation

# Creating sets
nums = {1, 2, 3, 4, 5}
empty_set = set()  # Note: {} creates a dict, not a set!

# Adding elements
nums.add(6)
nums.add(3)  # Duplicate - no effect
print(nums)  # {1, 2, 3, 4, 5, 6}

# Removing elements
nums.remove(3)    # Raises KeyError if not found
nums.discard(10)  # Safe - no error if not found

# Checking membership
if 2 in nums:
    print("Found 2")

# Iterating
for num in nums:
    print(num)

# Set from list (removes duplicates)
duplicates = [1, 2, 2, 3, 3, 3]
unique = set(duplicates)
print(unique)  # {1, 2, 3}

JavaScript Implementation

// Creating sets
const nums = new Set([1, 2, 3, 4, 5]);
const emptySet = new Set();

// Adding elements
nums.add(6);
nums.add(3); // Duplicate - no effect
console.log(nums); // Set {1, 2, 3, 4, 5, 6}

// Removing elements
nums.delete(3);

// Checking membership
if (nums.has(2)) {
  console.log('Found 2');
}

// Iterating
for (const num of nums) {
  console.log(num);
}

// Array to Set (removes duplicates)
const duplicates = [1, 2, 2, 3, 3, 3];
const unique = new Set(duplicates);
console.log([...unique]); // [1, 2, 3]

Common Patterns

Remove Duplicates from Array

def remove_duplicates(arr):
    return list(set(arr))

nums = [1, 2, 2, 3, 4, 4, 5]
print(remove_duplicates(nums))  # [1, 2, 3, 4, 5]

Check for Duplicates

def has_duplicates(arr):
    return len(arr) != len(set(arr))

print(has_duplicates([1, 2, 3]))     # False
print(has_duplicates([1, 2, 2, 3]))  # True

Find Unique Elements

def find_unique(arr):
    seen = set()
    unique = set()

    for num in arr:
        if num in seen:
            unique.discard(num)
        else:
            seen.add(num)
            unique.add(num)

    return unique

print(find_unique([1, 2, 3, 2, 4]))  # {1, 3, 4}

Time Complexity

*Worst case occurs with hash collisions, but is rare in practice.

Key Insight

Sets trade memory for speed. They're perfect when you need fast lookups and don't care about order or duplicates.