DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

HashSet

What Is a HashSet?

A HashSet is a collection that stores unique keys with O(1) average-case insert, lookup, and delete. It is a HashMap with no values — only keys. Every key either is in the set or it is not. Duplicates are silently ignored on insertion.

HashSet vs HashMap:

  HashMap: stores key → value pairs
    map.put("alice", 88)
    map.get("alice") → 88

  HashSet: stores keys only
    set.add("alice")
    set.contains("alice") → true / false

  HashSet is the answer to: "Have I seen this before?"
  HashMap is the answer to: "What do I know about this key?"

If your problem only asks whether something exists — not what it maps to — use a HashSet. It is simpler, uses less memory, and signals your intent clearly.

HashSet in Each Language

Language	Class / Type	Import
Java	`HashSet<E>`	`java.util.HashSet`
Python	`set`	Built-in, no import
C++	`unordered_set<T>`	`#include <unordered_set>`
JavaScript	`Set`	Built-in

Python's set is the most concise. Java's HashSet and C++'s unordered_set require explicit type parameters. JavaScript's Set is clean and supports any value type as an element.

Declaration and Initialization

Java

Try it out

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

public class HashSetDeclaration {

    public static void main(String[] args) {
        // Empty HashSet
        Set<String> names = new HashSet<>();

        // Initialize from a collection
        Set<Integer> nums = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));

        // Using Set interface (preferred — more flexible)
        Set<String> fruits = new HashSet<>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("cherry");

        // Duplicate — silently ignored
        fruits.add("apple");

        System.out.println("Fruits:        " + fruits);
        System.out.println("Size (no dup): " + fruits.size()); // 3, not 4
        System.out.println("Nums:          " + nums);
    }
}

Output:
Fruits:        [apple, banana, cherry]
Size (no dup): 3
Nums:          [1, 2, 3, 4, 5]

Core Operations

Add, Contains, Remove

Java

Try it out

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

public class HashSetOperations {

    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();

        // add — O(1) average, returns true if added, false if already present
        System.out.println(set.add(10)); // true  — new element
        System.out.println(set.add(20)); // true
        System.out.println(set.add(10)); // false — duplicate, ignored

        System.out.println("Set: " + set); // [10, 20]
        System.out.println("Size: " + set.size()); // 2

        // contains — O(1) average, the core operation
        System.out.println("Contains 10: " + set.contains(10)); // true
        System.out.println("Contains 99: " + set.contains(99)); // false

        // remove — O(1) average, returns true if removed, false if not present
        System.out.println("Remove 10: " + set.remove(10)); // true
        System.out.println("Remove 99: " + set.remove(99)); // false — not present
        System.out.println("After remove: " + set);          // [20]

        // isEmpty and clear
        System.out.println("isEmpty: " + set.isEmpty()); // false
        set.clear();
        System.out.println("After clear: " + set);       // []
        System.out.println("isEmpty: " + set.isEmpty()); // true
    }
}

Output:
Set: [10, 20]
Size: 2
Contains 10: true
Contains 99: false
Remove 10: true
Remove 99: false
After remove: [20]

The Core Use Case: O(1) Existence Check

The primary reason to use a HashSet is to replace an O(n) scan with an O(1) lookup. The pattern appears in dozens of interview problems.

Problem: Contains Duplicate — given an array, return true if any value appears more than once.

Brute force: O(n²)
  For each element, scan the rest of the array for a duplicate
  
HashSet approach: O(n)
  For each element, check if it is already in the set
  If yes → duplicate found
  If no → add it to the set and continue

Java

Try it out

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

public class ContainsDuplicate {

    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();

        for (int num : nums) {
            // contains is O(1) — replaces an O(n) linear scan
            if (seen.contains(num)) {
                return true;  // Found a duplicate — stop immediately
            }
            seen.add(num);
        }

        return false; // No duplicates
    }

    public static void main(String[] args) {
        System.out.println(containsDuplicate(new int[]{1, 2, 3, 1}));    // true
        System.out.println(containsDuplicate(new int[]{1, 2, 3, 4}));    // false
        System.out.println(containsDuplicate(new int[]{1, 1, 1, 3, 3})); // true
        System.out.println(containsDuplicate(new int[]{}));               // false
    }
}

Output:
true
false
true
false

Dry Run: Contains Duplicate on [1, 2, 3, 1]

seen = {}

num=1: 1 in seen? No  → seen = {1}
num=2: 2 in seen? No  → seen = {1, 2}
num=3: 3 in seen? No  → seen = {1, 2, 3}
num=1: 1 in seen? YES → return true ✓

Total: 4 checks, O(1) each → O(n) total
Brute force: would check 1 vs 2, 1 vs 3, 1 vs 1 → 6+ comparisons → O(n²)

Set Operations: Union, Intersection, Difference

Sets support mathematical set operations — combining, overlapping, and subtracting collections. These operations appear directly in interview problems involving "common elements," "elements in one but not both," or "all unique elements from both."

Java

Try it out

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

public class SetOperations {

    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        Set<Integer> b = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));

        // Union: all elements from both sets
        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);
        System.out.println("Union:        " + union); // {1,2,3,4,5,6,7,8}

        // Intersection: elements in both sets
        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);
        System.out.println("Intersection: " + intersection); // {4, 5}

        // Difference: elements in a but not in b
        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);
        System.out.println("Difference (a-b): " + difference); // {1, 2, 3}

        // Symmetric difference: elements in one but not both
        Set<Integer> symDiff = new HashSet<>(a);
        symDiff.addAll(b);                       // union
        Set<Integer> inter = new HashSet<>(a);
        inter.retainAll(b);                      // intersection
        symDiff.removeAll(inter);                // union - intersection
        System.out.println("Symmetric diff:   " + symDiff); // {1,2,3,6,7,8}

        // Subset check: is a ⊆ b?
        System.out.println("a ⊆ b: " + b.containsAll(a)); // false
        Set<Integer> small = new HashSet<>(Arrays.asList(4, 5));
        System.out.println("{4,5} ⊆ a: " + a.containsAll(small)); // true
    }
}

Output:
Union:             {1, 2, 3, 4, 5, 6, 7, 8}
Intersection:      {4, 5}
Difference (a-b):  {1, 2, 3}
Symmetric diff:    {1, 2, 3, 6, 7, 8}
{4,5} ⊆ a:        true

Deduplication — Removing Duplicates from an Array

Converting an array to a set and back is the fastest way to remove duplicates. Order is not preserved — if you need original order, use a different approach.

Java

Try it out

import java.util.*;

public class Deduplication {

    // Remove duplicates, order not preserved — O(n)
    public static int[] deduplicateUnordered(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        return set.stream().mapToInt(Integer::intValue).toArray();
    }

    // Remove duplicates, preserve insertion order — O(n)
    public static List<Integer> deduplicateOrdered(int[] nums) {
        Set<Integer> seen = new LinkedHashSet<>();  // preserves insertion order
        for (int num : nums) seen.add(num);
        return new ArrayList<>(seen);
    }

    // Remove duplicates in-place from sorted array — O(n), O(1) space
    public static int removeDuplicatesSorted(int[] nums) {
        if (nums.length == 0) return 0;
        int write = 1;  // next position to write a unique element

        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[read - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;  // new length
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

        System.out.println("Unordered dedup: " + Arrays.toString(deduplicateUnordered(arr)));
        System.out.println("Ordered dedup:   " + deduplicateOrdered(arr));

        int[] sorted = {1, 1, 2, 3, 3, 4};
        int newLen = removeDuplicatesSorted(sorted);
        System.out.println("In-place (sorted), new length: " + newLen);
        System.out.println("Array after:    " + Arrays.toString(Arrays.copyOf(sorted, newLen)));
    }
}

Output:
Ordered dedup:   [3, 1, 4, 5, 9, 2, 6]
Unique count:    7
Sorted dedup:    [1, 2, 3, 4]

Cycle Detection in Linked Lists

HashSet is the classic tool for detecting cycles — store every visited node; if you visit the same node twice, there is a cycle.

Java

Try it out

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

public class CycleDetection {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    // Detect cycle using HashSet — O(n) time, O(n) space
    public static boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();

        ListNode curr = head;
        while (curr != null) {
            if (visited.contains(curr)) {
                return true;  // Seen this node before — cycle!
            }
            visited.add(curr);
            curr = curr.next;
        }

        return false; // Reached null — no cycle
    }

    public static void main(String[] args) {
        // Build: 1 → 2 → 3 → 4 → 2 (cycle back to node 2)
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2; // cycle

        System.out.println("Has cycle: " + hasCycle(n1)); // true

        // No cycle: 1 → 2 → 3 → null
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        a.next = b; b.next = c;

        System.out.println("Has cycle: " + hasCycle(a)); // false
    }
}

Output:
Has cycle: true
Has cycle: false

Dry Run: Cycle Detection on 1→2→3→4→2

visited = {}

curr=node(1): node(1) in visited? No → visited={node1} → move to node(2)
curr=node(2): node(2) in visited? No → visited={node1,node2} → move to node(3)
curr=node(3): node(3) in visited? No → visited={node1,node2,node3} → move to node(4)
curr=node(4): node(4) in visited? No → visited={node1,node2,node3,node4} → move to node(2)
curr=node(2): node(2) in visited? YES → return true ✓

The HashSet stores node references (memory addresses), not values.
Nodes with the same value at different positions would NOT trigger a match.
This is why we store the node object itself, not its value.

Longest Consecutive Sequence

Problem: Find the length of the longest sequence of consecutive integers in an unsorted array. HashSet insight: Put all numbers in a set. For each number, only start counting if it is the beginning of a sequence (num-1 is not in the set). Then count consecutive numbers after it.

Java

Try it out

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

public class LongestConsecutive {

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

        int maxLen = 0;

        for (int num : numSet) {
            // Only start a sequence at the beginning of a run
            if (!numSet.contains(num - 1)) {
                int curr = num;
                int len  = 1;

                // Extend the sequence as far as possible
                while (numSet.contains(curr + 1)) {
                    curr++;
                    len++;
                }

                maxLen = Math.max(maxLen, len);
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{100,4,200,1,3,2})); // 4 (1,2,3,4)
        System.out.println(longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1})); // 9
        System.out.println(longestConsecutive(new int[]{})); // 0
    }
}

Output:
4
9
0

HashSet vs HashMap — When to Use Each

The choice is simple once you understand what information you need:

Use HashSet when:
  - "Does this element exist?" — existence check only
  - "Are there duplicates?" — deduplication
  - "What is the intersection / union / difference?" — set math
  - "Have I visited this node?" — cycle detection, graph traversal
  - You only care about presence, not what the key maps to

Use HashMap when:
  - "How many times does this appear?" — frequency counting
  - "What index was this first seen at?" — Two Sum, position tracking
  - "What group does this belong to?" — grouping, anagrams
  - "What is the value associated with this key?" — lookup by key
  - You need to store information alongside the key

Quick test: if your value would always be `true` or just `1`,
           use HashSet instead of HashMap<K, Boolean> or HashMap<K, Integer>.

HashSet Operation Complexity Summary

Operation	Average	Worst	Notes
`add` / `insert`	O(1)	O(n)	Worst case: all keys collide
`contains` / `has` / `count`	O(1)	O(n)	The core operation
`remove` / `erase` / `delete`	O(1)	O(n)	Returns bool if removed
`size` / `len`	O(1)	O(1)	Stored as a field
Iteration	O(n)	O(n)	Visit every element
Union	O(n + m)	O(n + m)	Add all elements from both
Intersection	O(min(n, m))	O(n × m)	Check each of smaller set against larger
Difference	O(n)	O(n × m)	Check each element of first set

Common Mistakes Beginners Make

Using {} in Python to create an empty set. {} creates an empty dict, not an empty set. To create an empty set, always use set(). {1, 2, 3} is a set literal with values — that is fine. But {} alone is always an empty dict.

Checking for cycles by comparing node values instead of node references. In a linked list, two different nodes can have the same value. Storing node.val in the visited set would falsely report a cycle when a value repeats. Always store the node object itself (or its memory address), not its value.

Using List instead of Set for existence checks in a loop. list.contains(x) in Java is O(n). If you call it inside a loop of n iterations, total cost is O(n²). Convert to a HashSet first — O(n) to build, then O(1) per lookup. The pattern if (list.contains(x)) inside a loop is one of the most common hidden O(n²) bugs.

Iterating and modifying a set simultaneously in Java. Adding or removing elements while iterating with a for-each throws ConcurrentModificationException. Collect elements to add/remove in a separate list, then apply changes after the loop.

Expecting ordered iteration from HashSet. HashSet / unordered_set do not guarantee iteration order. Java's LinkedHashSet preserves insertion order. Python's set does not preserve order (unlike dict which does since 3.7). JavaScript's Set does preserve insertion order.

Interview Questions

Q: What is the difference between HashSet and HashMap in terms of implementation?

Both use the same underlying hash table structure. A HashSet is essentially a HashMap where every key maps to a dummy sentinel value (Java's HashSet internally uses a HashMap with a shared PRESENT object as the value). The extra value field is wasted space, which is why HashSet uses slightly less memory per entry — it stores only keys, not key-value pairs. The hash function, collision handling, load factor, and rehashing are identical.

Q: Why does the contains-duplicate solution use a HashSet instead of a HashMap?

Because we only need to know whether a value has been seen before — not what index it was at or how many times. That is a presence question, not a mapping question. Using HashMap<Integer, Boolean> with value true would work but wastes memory and signals incorrect intent. When the value you would store is always the same constant (true, 1, a dummy), use a HashSet.

Q: How does the longest consecutive sequence algorithm achieve O(n) despite the inner while loop?

The outer loop iterates over each number once. The inner while loop only runs when the number is the start of a sequence — that is, when num - 1 is not in the set. Each number can only be the extension of one sequence, so across all outer loop iterations, the inner loop visits each number at most once total. Total inner loop iterations: O(n). Combined with the O(n) outer loop: O(n) overall.

FAQs

Is Python's set ordered?

No. Python's set does not preserve insertion or any other order — elements can be iterated in any sequence. This is unlike Python's dict (ordered since 3.7). If you need a set-like structure with insertion order, use dict.fromkeys(iterable) which gives ordered unique elements. LinkedHashSet in Java and JavaScript's Set preserve insertion order.

Can a HashSet contain null elements?

In Java, HashSet allows exactly one null element. In Python, None is a valid set member (it is hashable). In C++, unordered_set does not support nullptr for pointer types without custom handling. In JavaScript, Set allows both null and undefined as members (each counted once). Always check the language's behavior if null membership matters for your problem.

When would you use TreeSet over HashSet in Java?

Use TreeSet when you need elements in sorted order during iteration, when you need first() / last() (minimum/maximum), or when you need range queries like headSet(x) (all elements less than x) or tailSet(x) (all elements ≥ x). TreeSet operations are O(log n) — slower than HashSet's O(1) average — but it maintains sorted order as a red-black tree.

Quick Quiz

Question 1: set.add(x) in Java returns false. What does this mean?

›A) The add failed due to a capacity error
›B) x was already in the set — the duplicate was ignored
›C) x is null — null is not allowed
›D) The set is read-only

Answer: B) x was already in the set. HashSet.add() returns false when the element already exists (duplicate ignored) and true when a new element was successfully added. This return value lets you detect whether an element was new or a duplicate in a single operation.

Question 2: In Python, what does {} create?

›A) An empty set
›B) An empty dict
›C) A set with a default element
›D) A syntax error

Answer: B) An empty dict. {} is Python's empty dict literal. To create an empty set, you must write set(). {1, 2, 3} is a set literal with values — only the empty case is ambiguous.

Question 3: You need to find the intersection of two arrays. The most efficient approach using a HashSet is:

›A) Sort both arrays and use two pointers — O(n log n)
›B) Put one array in a HashSet, scan the other and collect matches — O(n + m)
›C) Nested loops checking every pair — O(n × m)
›D) Put both in a HashSet, their intersection is automatic — O(1)

Answer: B) Put one array in a HashSet, scan the other. Build a HashSet from the first array in O(n). For each element in the second array, check set.contains(x) in O(1). Collect matches. Total: O(n + m). This is optimal — you must read every element at least once.

Question 4: In the cycle detection algorithm, why do we store node objects (references) in the HashSet rather than node values?

›A) Node objects are smaller and more memory-efficient
›B) Different nodes can have the same value — storing values would give false positives
›C) Java's HashSet cannot store integers directly
›D) Node references hash faster than integer values

Answer: B) Different nodes can have the same value — storing values would give false positives. A linked list like 1→2→1→3 has two nodes with value 1. If we stored values, we would report a cycle when the second 1 appears — but there is no cycle. We store node references (memory addresses) so that only revisiting the exact same node object triggers a cycle detection.

Summary

A HashSet is a key-only hash table that answers the question "have I seen this before?" in O(1) average time. It is simpler than a HashMap and the right choice whenever you only need presence — not what a key maps to.

The key operations and patterns:

›add / insert — O(1) average, ignores duplicates silently
›contains / has / count — O(1) average — the core operation
›remove / erase / delete — O(1) average
›Existence check replaces O(n) linear scan — the fundamental speedup
›Deduplication — convert to set and back — O(n)
›Set operations — union O(n+m), intersection O(min(n,m)), difference O(n)
›Cycle detection — store visited nodes (references, not values)
›Longest consecutive — put all in set, only count from sequence starts

Use HashSet when you only care about presence. Use HashMap when you need to associate data with the key. Never use List.contains() inside a loop — convert to HashSet first.

In the next topic, you will explore Collision Handling — the two fundamental strategies (chaining and open addressing) that keep hash tables functional when multiple keys land at the same index.

←

PreviousHashMap

NextCollision Handling

→