Classic Set Problems

1. Contains Duplicate

Problem: Return true if any value appears at least twice.

def contains_duplicate(nums):
    return len(nums) != len(set(nums))

# Alternative - early exit
def contains_duplicate_v2(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

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

2. Two Sum (Set Approach)

Problem: Find two numbers that add up to target.

def two_sum(nums, target):
    seen = set()

    for num in nums:
        complement = target - num
        if complement in seen:
            return True
        seen.add(num)

    return False

print(two_sum([2, 7, 11, 15], 9))   # True (2 + 7)
print(two_sum([2, 7, 11, 15], 100)) # False

3. Longest Consecutive Sequence

Problem: Find the length of the longest consecutive sequence.

def longest_consecutive(nums):
    if not nums:
        return 0

    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # Only start sequence from the beginning
        if num - 1 not in num_set:
            current = num
            length = 1

            # Extend sequence
            while current + 1 in num_set:
                current += 1
                length += 1

            max_length = max(max_length, length)

    return max_length

nums = [100, 4, 200, 1, 3, 2]
print(longest_consecutive(nums))  # 4 (1,2,3,4)

Key Insight: Use set for O(1) lookups, and only start counting from sequence beginnings.

4. Happy Number

Problem: Determine if a number is "happy" (eventually reaches 1 through sum of digit squares).

def is_happy(n):
    seen = set()

    while n != 1 and n not in seen:
        seen.add(n)
        n = sum(int(digit) ** 2 for digit in str(n))

    return n == 1

print(is_happy(19))  # True: 19 → 82 → 68 → 100 → 1
print(is_happy(2))   # False: enters a cycle

5. Intersection of Two Arrays

Problem: Find the intersection of two arrays.

def intersection(nums1, nums2):
    return list(set(nums1) & set(nums2))

# Alternative with sets
def intersection_v2(nums1, nums2):
    set1 = set(nums1)
    result = set()

    for num in nums2:
        if num in set1:
            result.add(num)

    return list(result)

nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersection(nums1, nums2))  # [2]

6. Single Number

Problem: Find the element that appears once (all others appear twice).

def single_number(nums):
    """Using set - space O(n)"""
    return 2 * sum(set(nums)) - sum(nums)

# Better: Using XOR - space O(1)
def single_number_xor(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

nums = [4, 1, 2, 1, 2]
print(single_number(nums))      # 4
print(single_number_xor(nums))  # 4

7. Valid Sudoku

Problem: Check if a Sudoku board is valid.

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for r in range(9):
        for c in range(9):
            if board[r][c] == '.':
                continue

            num = board[r][c]
            box_idx = (r // 3) * 3 + (c // 3)

            # Check if already seen in row, col, or box
            if (num in rows[r] or
                num in cols[c] or
                num in boxes[box_idx]):
                return False

            # Add to sets
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_idx].add(num)

    return True

8. Group Anagrams

Problem: Group strings that are anagrams of each other.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)

    for s in strs:
        # Use sorted string as key
        key = ''.join(sorted(s))
        groups[key].append(s)

    return list(groups.values())

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs))
# [["eat","tea","ate"], ["tan","nat"], ["bat"]]

9. Find All Duplicates

Problem: Find all elements that appear twice (using set).

def find_duplicates(nums):
    seen = set()
    duplicates = set()

    for num in nums:
        if num in seen:
            duplicates.add(num)
        else:
            seen.add(num)

    return list(duplicates)

nums = [4, 3, 2, 7, 8, 2, 3, 1]
print(find_duplicates(nums))  # [2, 3]

10. Jewels and Stones

Problem: Count how many stones are jewels.

def num_jewels_in_stones(jewels, stones):
    jewel_set = set(jewels)
    return sum(stone in jewel_set for stone in stones)

jewels = "aA"
stones = "aAAbbbb"
print(num_jewels_in_stones(jewels, stones))  # 3

Common Set Problem Patterns

1. Duplicate Detection: Track seen elements
2. Membership Testing: Fast O(1) lookups
3. Cycle Detection: Track visited states
4. Uniqueness: Remove duplicates, count unique
5. Set Operations: Intersection, union, difference
6. Complement Finding: Two sum, pair problems