Complexity Analysis and Optimization Using HashSet in Java

Introduction

Greetings, programming enthusiast! In this unit, we're embarking on a thrilling numerical quest, where unidentified bridges connect the islands of data. On these bridges, we'll see hashes and bins, all converging into sets! Throughout our journey, we'll utilize the fundamental concepts of the Java Collections Framework to formulate an optimal solution. So, fasten your seatbelt and get ready to solve problems!

Task Statement

The task for this unit is to devise a Java function that accepts two lists containing unique integers and returns another list containing the elements common to both input lists. This task provides an intriguing perspective on deriving similarities between two data sequences, a scenario commonly encountered in data comparisons and analytics. For illustration, suppose we're given two lists: Java List<Integer> list1 = Arrays.asList(1, 2, 3, 5, 8, 13, 21, 34); List<Integer> list2 = Arrays.asList(2, 3, 5, 7, 13, 21, 31); List<Integer> list1 = Arrays.asList(1, 2, 3, 5, 8, 13, 21, 34); List<Integer> list2 = Arrays.asList(2, 3, 5, 7, 13, 21, 31); The commonElements(list1, list2) function should comb through these arrays of integers and extract the common elements between them. The expected outcome in this case should be: Java List<Integer> result = Arrays.asList(2, 3, 5, 13, 21); List<Integer> result = Arrays.asList(2, 3, 5, 13, 21);

Brute Force Solution and Complexity Analysis

O(n \cdot m)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CommonElements { public static List<Integer> commonElementsSlow(List<Integer> list1, List<Integer> list2) { List<Integer> common = new ArrayList<>(); // List to store common elements for (Integer num1 : list1) { for (Integer num2 : list2) { if (num1.equals(num2)) { common.add(num1); break; // Break inner loop as we found the number in list2 } } } return common; } public static void main(String[] args) { List<Integer> list1 = Arrays.asList(1, 2, 3, 5, 8, 13, 21, 34); List<Integer> list2 = Arrays.asList(2, 3, 5, 7, 13, 21, 31); List<Integer> result = commonElementsSlow(list1, list2); System.out.println(result); // Prints: [2, 3, 5, 13, 21] } }

Additional HashSet Methods

The HashSet in Java is not only efficient but also provides a plethora of useful methods for performing various operations. Let's explore some of these practical methods:

1. Insertion

The add method allows you to add elements to a HashSet. If the element already exists, the insertion does nothing. The average time complexity for insertion is $O(1)$ .

Java

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

public class HashSetInsertExample {
    public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<>(Arrays.asList(1, 2, 3));
        mySet.add(4);  // O(1)
        mySet.add(2);  // O(1) but this will have no effect since 2 is already in the set

        System.out.println(mySet);  // Prints: [1, 2, 3, 4] (order may vary)
    }
}

2. Removal

The remove method removes elements from a HashSet. If the element does not exist, the remove operation does nothing. The average time complexity for removal is $O(1)$ .

Java

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

public class HashSetRemoveExample {
    public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<>(Arrays.asList(1, 2, 3, 4));
        mySet.remove(3);  // O(1)
        mySet.remove(5);  // O(1) but this will have no effect since 5 is not in the set

        System.out.println(mySet);  // Prints: [1, 2, 4] (order may vary)
    }
}

3. Checking Membership

The contains method checks for the existence of an element in a HashSet. It returns true if the element is found, otherwise, it returns false. The average time complexity for this operation is $O(1)$ .

Java

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

public class HashSetContainsExample {
    public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        System.out.println(mySet.contains(3));  // O(1), prints: true
        System.out.println(mySet.contains(6));  // O(1), prints: false
    }
}

4. Size

The size method returns the number of elements in a HashSet. The time complexity for this operation is $O(1)$ .

Java

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

public class HashSetSizeExample {
    public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        System.out.println(mySet.size());  // O(1), prints: 5
    }
}

5. Clear

The clear method removes all elements from a HashSet. The average time complexity for this operation is $O(n)$ , where n is the number of elements in the set.

Java

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

public class HashSetClearExample {
    public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        mySet.clear();  // O(n)
        System.out.println(mySet.size());  // O(1), prints: 0
    }
}

Knowing these operations will allow you to use Java HashSets to their full potential and help you devise efficient solutions for a variety of problems.

Introduction

Task Statement

Brute Force Solution and Complexity Analysis

Join the 1M+ learners on CodeSignal

Introduction to HashSet Solution

Solution Building: Step 1

Solution Building: Step 2

Additional HashSet Methods

Lesson Summary