HashSets in Java

HashSets are a fundamental data structure in Java and are widely used in Leetcode problems. They store unique elements and provide efficient lookup, insertion, and deletion operations.

Table of Contents

1. HashSet Basics
2. Common HashSet Operations
3. Common Leetcode Patterns
4. Time and Space Complexity
5. Related Leetcode Questions

HashSet Basics

• Definition: A HashSet is a collection that stores unique elements. It uses hashing to compute an index into an array of buckets or slots, from which the desired element can be found.

• Declaration:

  HashSet<Integer> set = new HashSet<>();

• Key Characteristics:

  • Elements are unique.
  • Allows one null element.
  • Unordered collection (no guarantee of order).

Common HashSet Operations

1. Inserting an Element

• Method: add(E e)

• Example:

  set.add(1);
  set.add(2);

• Time Complexity: O(1) (average case), O(n) (worst case due to collisions)

• Space Complexity: O(1)

2. Checking if an Element Exists

• Method: contains(Object o)

• Example:

  boolean exists = set.contains(1); // exists = true

• Time Complexity: O(1) (average case), O(n) (worst case due to collisions)

• Space Complexity: O(1)

3. Removing an Element

• Method: remove(Object o)

• Example:

  set.remove(1); // Removes the element 1

• Time Complexity: O(1) (average case), O(n) (worst case due to collisions)

• Space Complexity: O(1)

4. Iterating Over a HashSet

• Using Iterator:

  Iterator<Integer> iterator = set.iterator();
  while (iterator.hasNext()) {
      System.out.println(iterator.next());
  }

• Using Enhanced For Loop:

  for (Integer element : set) {
      System.out.println(element);
  }

• Time Complexity: O(n)

• Space Complexity: O(1)

5. Size of the HashSet

• Method: size()

• Example:

  int size = set.size(); // size = 1

• Time Complexity: O(1)

• Space Complexity: O(1)

6. Checking if the HashSet is Empty

• Method: isEmpty()

• Example:

  boolean isEmpty = set.isEmpty(); // isEmpty = false

• Time Complexity: O(1)

• Space Complexity: O(1)

Common Leetcode Patterns

1. Finding Duplicates

• Used for problems like checking for duplicates, finding the first duplicate, etc.

• Example:

  HashSet<Integer> set = new HashSet<>();
  for (int num : nums) {
      if (set.contains(num)) {
          return true; // Duplicate found
      }
      set.add(num);
  }
  return false;

• Related Questions:

  • Contains Duplicate
  • Find the Duplicate Number

2. Finding Unique Elements

• Used for problems like finding unique elements, removing duplicates, etc.

• Example:

  HashSet<Integer> set = new HashSet<>();
  for (int num : nums) {
      set.add(num);
  }
  return set.size();

• Related Questions:

  • Single Number
  • Remove Duplicates from Sorted Array

3. Intersection of Two Sets

• Used for problems like finding common elements between two arrays, intersection of two linked lists, etc.

• Example:

  HashSet<Integer> set1 = new HashSet<>();
  for (int num : nums1) {
      set1.add(num);
  }
  HashSet<Integer> set2 = new HashSet<>();
  for (int num : nums2) {
      set2.add(num);
  }
  set1.retainAll(set2); // Intersection
  return new ArrayList<>(set1);

• Related Questions:

  • Intersection of Two Arrays
  • Intersection of Two Linked Lists

4. Union of Two Sets

• Used for problems like combining two arrays, finding all unique elements, etc.

• Example:

  HashSet<Integer> set = new HashSet<>();
  for (int num : nums1) {
      set.add(num);
  }
  for (int num : nums2) {
      set.add(num);
  }
  return new ArrayList<>(set);

• Related Questions:

  • Union of Two Arrays

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Insert (add())	O(1) (average)	O(1)
Contains (contains())	O(1) (average)	O(1)
Remove (remove())	O(1) (average)	O(1)
Iteration	O(n)	O(1)
Size (size())	O(1)	O(1)
Is Empty (isEmpty())	O(1)	O(1)

Related Leetcode Questions

Easy

1. Contains Duplicate
2. Single Number
3. Intersection of Two Arrays

Medium

1. Find the Duplicate Number
2. Longest Substring Without Repeating Characters
3. Happy Number

Hard

1. Longest Consecutive Sequence
2. First Missing Positive
3. Insert Delete GetRandom O(1)