Sets

Definition

---

Big O Complexity

---

When to Use

---

Pros and Cons

---

Implementation

HashSet (Simplified)

// HashSet is typically implemented using a HashMap
public class MyHashSet<E> {
    private static final Object PRESENT = new Object();
    private HashMap<E, Object> map;

    public MyHashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean remove(E e) {
        return map.remove(e) == PRESENT;
    }

    public boolean contains(E e) {
        return map.containsKey(e);
    }

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }

    public void clear() {
        map.clear();
    }
}

Bit Set (for integers in range)

// Efficient for dense integer sets
public class BitSet {
    private long[] bits;
    private int size;

    public BitSet(int maxValue) {
        this.bits = new long[(maxValue + 63) / 64];
    }

    public void add(int value) {
        int index = value / 64;
        int bit = value % 64;
        if ((bits[index] & (1L << bit)) == 0) {
            bits[index] |= (1L << bit);
            size++;
        }
    }

    public boolean contains(int value) {
        int index = value / 64;
        int bit = value % 64;
        return (bits[index] & (1L << bit)) != 0;
    }

    public void remove(int value) {
        int index = value / 64;
        int bit = value % 64;
        if ((bits[index] & (1L << bit)) != 0) {
            bits[index] &= ~(1L << bit);
            size--;
        }
    }
}

---

Java Collections Usage

// HashSet - unordered, O(1) operations
Set<String> hashSet = new HashSet<>();
hashSet.add("apple");
hashSet.add("banana");
hashSet.add("apple");  // Ignored (duplicate)
hashSet.contains("apple");  // true
hashSet.remove("apple");
hashSet.size();  // 1

// Initialize from collection
Set<Integer> fromList = new HashSet<>(Arrays.asList(1, 2, 3, 2, 1));
// Result: {1, 2, 3}

// LinkedHashSet - maintains insertion order
Set<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("c");
linkedSet.add("a");
linkedSet.add("b");
// Iteration order: c, a, b

// TreeSet - sorted order
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(2);
treeSet.add(8);
// Iteration order: 2, 5, 8

// TreeSet navigation methods
TreeSet<Integer> navSet = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));
navSet.first();           // 1 - smallest
navSet.last();            // 9 - largest
navSet.floor(4);          // 3 - largest ≤ 4
navSet.ceiling(4);        // 5 - smallest ≥ 4
navSet.lower(4);          // 3 - largest < 4
navSet.higher(4);         // 5 - smallest > 4
navSet.headSet(5);        // [1, 3] - elements < 5
navSet.tailSet(5);        // [5, 7, 9] - elements ≥ 5
navSet.subSet(3, 7);      // [3, 5] - elements in [3, 7)
navSet.descendingSet();   // [9, 7, 5, 3, 1]

// Custom comparator
Set<String> customSet = new TreeSet<>((a, b) -> b.compareTo(a));  // Reverse order

---

Set Operations

Set<Integer> setA = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> setB = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));

// Union: A ∪ B
Set<Integer> union = new HashSet<>(setA);
union.addAll(setB);  // {1, 2, 3, 4, 5, 6, 7, 8}

// Intersection: A ∩ B
Set<Integer> intersection = new HashSet<>(setA);
intersection.retainAll(setB);  // {4, 5}

// Difference: A - B
Set<Integer> difference = new HashSet<>(setA);
difference.removeAll(setB);  // {1, 2, 3}

// Symmetric Difference: (A - B) ∪ (B - A)
Set<Integer> symDiff = new HashSet<>(setA);
symDiff.addAll(setB);
Set<Integer> temp = new HashSet<>(setA);
temp.retainAll(setB);
symDiff.removeAll(temp);  // {1, 2, 3, 6, 7, 8}

// Subset check: A ⊆ B
boolean isSubset = setB.containsAll(setA);  // false

// Disjoint check: A ∩ B = ∅
boolean isDisjoint = Collections.disjoint(setA, setB);  // false

---

Common Patterns & Problems

Remove Duplicates

// From array
public int[] removeDuplicates(int[] nums) {
    return Arrays.stream(nums)
        .distinct()
        .toArray();
}

// From list
public List<Integer> removeDuplicates(List<Integer> list) {
    return new ArrayList<>(new LinkedHashSet<>(list));  // Preserves order
}

Find Duplicates

public List<Integer> findDuplicates(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    List<Integer> duplicates = new ArrayList<>();

    for (int num : nums) {
        if (!seen.add(num)) {  // add returns false if already present
            duplicates.add(num);
        }
    }
    return duplicates;
}

Intersection of Two Arrays

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    for (int num : nums1) set1.add(num);

    Set<Integer> result = new HashSet<>();
    for (int num : nums2) {
        if (set1.contains(num)) {
            result.add(num);
        }
    }

    return result.stream().mapToInt(i -> i).toArray();
}

Contains Duplicate II (Within k distance)

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> window = new HashSet<>();

    for (int i = 0; i < nums.length; i++) {
        if (i > k) {
            window.remove(nums[i - k - 1]);
        }
        if (!window.add(nums[i])) {
            return true;  // Duplicate found within window
        }
    }
    return false;
}

Longest Consecutive Sequence

public int longestConsecutive(int[] nums) {
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) numSet.add(num);

    int longest = 0;

    for (int num : numSet) {
        // Only start counting from sequence beginning
        if (!numSet.contains(num - 1)) {
            int currentNum = num;
            int currentStreak = 1;

            while (numSet.contains(currentNum + 1)) {
                currentNum++;
                currentStreak++;
            }
            longest = Math.max(longest, currentStreak);
        }
    }
    return longest;
}

Valid Sudoku

public boolean isValidSudoku(char[][] board) {
    Set<String> seen = new HashSet<>();

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char c = board[i][j];
            if (c != '.') {
                String row = c + " in row " + i;
                String col = c + " in col " + j;
                String box = c + " in box " + i/3 + "-" + j/3;

                if (!seen.add(row) || !seen.add(col) || !seen.add(box)) {
                    return false;
                }
            }
        }
    }
    return true;
}

Group Anagrams (Using Set for lookup)

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();

    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }

    return new ArrayList<>(map.values());
}

Word Break (Using Set for dictionary)

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

---

Tips & Tricks

---