⚡

Lab Exercise: Algorithm Optimization

Transform O(n²) to O(n) using HashSets

🎯The Challenge

Performance Problem Detected!

Your colleague wrote a method called findDuplicates() that identifies duplicate numbers in an array. It works correctly, but it's way too slow for large datasets.

The current implementation uses nested loops, giving it a time complexity of O(n²). For an array of 10,000 elements, that's roughly 50 million comparisons!

Your Mission

Rewrite the findDuplicates() method to achieve O(n) time complexity by using a HashSet.

The method should still return an ArrayList<Integer> containing all duplicate values
Use a HashSet to track which numbers you've already seen
Process the array in a single pass
Each duplicate should appear only once in the result

Success Criteria

Time Complexity: O(n) - single pass through the array
Space Complexity: O(n) - using HashSets for tracking
Correctness: Produces the same output as the original method
Efficiency: Can handle arrays of 10,000+ elements in milliseconds

📝Starter Code (The Slow Version)

Here's the current implementation. Study it carefully to understand why it's O(n²):

import java.util.ArrayList;

public class DuplicateFinder {
    
    /**
     * SLOW VERSION: O(n²) time complexity
     * This method uses nested loops - every element is compared with every other element
     */
    public static ArrayList<Integer> findDuplicates(int[] numbers) {
        ArrayList<Integer> duplicates = new ArrayList<>();
        
        // Outer loop: Pick each element
        for (int i = 0; i < numbers.length; i++) {
            // Inner loop: Compare with all other elements
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] == numbers[j]) {
                    // Found a duplicate! But check if we already added it
                    if (!duplicates.contains(numbers[i])) {
                        duplicates.add(numbers[i]);
                    }
                }
            }
        }
        
        return duplicates;
    }
    
    public static void main(String[] args) {
        int[] testData = {5, 2, 8, 2, 9, 5, 7, 3, 5, 8};
        ArrayList<Integer> result = findDuplicates(testData);
        System.out.println("Duplicates found: " + result);
    }
}

Analysis: The nested loop structure means for each of the n elements, we potentially check all other n elements. This gives us n × n = n² operations. The contains() check on ArrayList makes it even worse, adding another O(n) operation inside the loops!

🎓Key Takeaways

1.Nested loops are expensive: They create quadratic time complexity, which doesn't scale well
2.HashSet is your friend: Constant-time lookups transform O(n²) to O(n)
3.Space-time tradeoff: We use extra memory (HashSets) to gain massive speed improvements
4.Real-world impact: The difference between O(n²) and O(n) can be the difference between seconds and milliseconds

Keep reading — this lesson marks itself done automatically.