HashSets & Set Logic

1. Introduction: The Bouncer at the Club

If a HashMap is a librarian mapping titles to exact shelf locations, a HashSet is the bouncer at an exclusive club holding a VIP list. He doesn't care what you do inside the club, and he doesn't assign you a specific seat. He only cares about one question: "Are you on the list?"

In computer science, a Set is a collection of unique elements. It is mathematically impossible for a Set to contain duplicate values. In Java, a HashSet provides $O(1)$ constant time operations for add(), remove(), and contains().

While HashMaps are used for tracking data mappings and frequencies, HashSets are used for Existence Checks, Deduplication, and finding mathematical Intersections and Unions.

2. Core Concept: Under the Hood of a HashSet

How does Java implement a HashSet to guarantee $O(1)$ operations? It cheats!

If you look at the source code for Java's java.util.HashSet, you will see that it literally just creates a java.util.HashMap internally. When you write set.add("Apple"), Java actually executes map.put("Apple", PRESENT), where PRESENT is just a dummy Object that takes up minimal memory.

Therefore, a HashSet shares all the exact same properties as a HashMap:

• It relies on .hashCode() and .equals().
• Elements are completely unordered.
• It can handle collisions using Linked Lists/Trees.
• Adding a duplicate element silently overwrites the previous entry (effectively doing nothing).

3. Beginner Code Example: Deduplication and Intersection

The two most common primitive uses of a HashSet are removing duplicates from an array and finding common elements between two arrays.

Problem Statement 1: (LeetCode 217) Contains Duplicate. Given an integer array nums, return true if any value appears at least twice in the array.

import java.util.HashSet;
import java.util.Set;

public class DuplicateCheck {
    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            // set.add() returns false if the element was ALREADY in the set!
            if (!set.add(num)) {
                return true; 
            }
        }
        return false;
    }
}

Problem Statement 2: (LeetCode 349) Intersection of Two Arrays. Given two integer arrays nums1 and nums2, return an array of their intersection (unique elements present in both).

import java.util.HashSet;
import java.util.Set;

public class ArrayIntersection {
    public static int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num); // Add all elements of first array to a set
        }
        
        Set<Integer> resultSet = new HashSet<>();
        for (int num : nums2) {
            // O(1) existence check!
            if (set1.contains(num)) {
                resultSet.add(num);
            }
        }
        
        // Convert Set back to int[]
        int[] result = new int[resultSet.size()];
        int i = 0;
        for (int num : resultSet) {
            result[i++] = num;
        }
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(N + M)$. We iterate through both arrays.
• Space Complexity: $O(N + M)$ to store the sets.

4. Intermediate Code Example: Longest Consecutive Sequence

Problem Statement: (LeetCode 128) Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence (e.g., [100, 4, 200, 1, 3, 2] yields [1, 2, 3, 4], length 4). You must write an algorithm that runs in $O(N)$ time.

The Sorting Trap: Sorting the array makes this trivial, but sorting takes $O(N \log N)$. The Insight: If we put everything in a HashSet, we can check if a number exists in $O(1)$ time. But how do we avoid checking every sequence multiple times? We only start counting a sequence if the current number is the start of a sequence! How do we know it's the start? If num - 1 does NOT exist in the set!

import java.util.HashSet;
import java.util.Set;

public class LongestConsecutive {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        
        int longestStreak = 0;
        
        for (int num : set) {
            // Is this the start of a sequence?
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                // Keep counting upwards!
                while (set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
}

5. Advanced Code Example: Sliding Window with Sets

HashSets pair perfectly with Sliding Window algorithms to guarantee uniqueness within a dynamic window.

Problem Statement: (LeetCode 3) Longest Substring Without Repeating Characters. Given a string s, find the length of the longest substring without repeating characters.

The Insight: Maintain a HashSet that represents the active window. Expand the right pointer. If s.charAt(right) is NOT in the set, add it and update the max length. If it IS in the set, we have a duplicate! We must shrink the window from the left until the duplicate is completely removed from the set.

import java.util.HashSet;
import java.util.Set;

public class LongestUniqueSubstring {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> windowSet = new HashSet<>();
        int left = 0, maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            // While the duplicate exists, shrink the window from the left
            while (windowSet.contains(currentChar)) {
                windowSet.remove(s.charAt(left));
                left++;
            }
            
            // Now it's safe to add the new character
            windowSet.add(currentChar);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. Even with the while loop, every character is added to the set once and removed at most once. (2N operations).
• Space Complexity: $O(\min(N, M))$ where $M$ is the size of the alphabet (e.g., 26 for lowercase letters, 128 for ASCII).

6. Common Mistakes Beginners Make

1. Trying to get the element at a specific index

   • The Mistake: int first = set.get(0);
   • Why it's wrong: Sets have absolutely no concept of order or indices. They are scattered randomly in memory based on their hash code.
   • The Fix: You must use an Iterator, or a for-each loop to access elements.

2. Using a Set when counts actually matter

   • The Mistake: Using a HashSet to solve the "Intersection of Two Arrays II" (LeetCode 350) which requires returning duplicate intersections.
   • Why it's wrong: Sets obliterate duplicates. If nums1 = [1, 2, 2, 1] and nums2 = [2, 2], the result should be [2, 2]. A HashSet will reduce everything to [2] and fail. You must use a HashMap to track the actual frequency counts.

3. Modifying an Object while it is in the Set

   • The Mistake: Adding a custom Person object to a set, then changing their name property.
   • Why it's wrong: Changing the property changes the Hash Code. The object is now "lost" inside the HashSet's internal array, causing .contains() to return false and causing memory leaks.

7. Interview Q&A

Q1: How do you maintain insertion order in a Set? Answer: Use a LinkedHashSet. It maintains a doubly-linked list running through all of its entries. This keeps the $O(1)$ lookup time but guarantees that iterating over the set will return elements in the exact order they were inserted.

Q2: How do you maintain sorted order in a Set? Answer: Use a TreeSet. It is backed by a Red-Black Tree. Elements are mathematically sorted. However, because it is a tree, add(), remove(), and contains() degrade from $O(1)$ to $O(\log N)$ time.

Q3: Can we find the Union and Difference of two sets in Java? Answer: Yes! Java's Set interface has powerful built-in math methods:

• Union: set1.addAll(set2) (Adds all elements from set2).
• Intersection: set1.retainAll(set2) (Removes elements from set1 that are not in set2).
• Difference: set1.removeAll(set2) (Removes all elements in set1 that exist in set2).

8. Practice Problems

1. Contains Duplicate (LeetCode 217)
   • Goal: Basic $O(1)$ insertion and existence check.
2. Intersection of Two Arrays (LeetCode 349)
   • Goal: Implement the Intersection math pattern.
3. Longest Consecutive Sequence (LeetCode 128)
   • Hint: Master the !set.contains(num - 1) sequence-start logic.

9. Summary

• The VIP List: HashSets are for answering the $O(1)$ question: "Have I seen this before?"
• Unordered: You cannot fetch the "first" or "last" element of a standard HashSet.
• Deduplication: Passing an array with duplicates into a HashSet instantly creates an array of purely unique items.
• Sliding Window Synergy: HashSets are the standard data structure for tracking "currently active" unique elements inside a dynamic Sliding Window.