Guided Project: Hash Tables II

Project Overview

Learning Goals

Understand frequency counting with hash tables
Apply hash tables to find non-repeating elements
Group elements by computed values
Optimize time and space complexity

Prerequisites

JavaScript Map and Set
Hash table concept understanding
Basic time complexity analysis
Array and string manipulation

Hash Table Use Cases

Common Patterns

Frequency counting
De-duplication
Grouping by properties
Two-sum pattern
Caching/memoization

Optimal Data Structures

Map: Key-value pairs with any type of key
Set: Collection of unique values
Object: Simple string-keyed lookups
WeakMap/WeakSet: When object references shouldn't prevent garbage collection

First Non-Repeating Character

Implementation

                            /**
 * Find the first non-repeating character in a string
 * @param str Input string
 * @return First non-repeating character or null
 */
public static Character firstNonRepeatingChar(String str) {
    Map<Character, Integer> charCount = new HashMap<>();
    for (char c : str.toCharArray()) {
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }
    for (char c : str.toCharArray()) {
        if (charCount.get(c) == 1) {
            return c;
        }
    }
    return null;
}
                        

Time & Space Complexity:

Time Complexity: O(n) - requires two passes through the string
Space Complexity: O(k) - where k is the number of unique characters (at most the size of the character set)

Group Anagrams

Implementation

                            /**
 * Group anagrams together from an array of strings
 * @param strs Array of strings
 * @return Groups of anagrams
 */
public static List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> anagramGroups = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String sortedStr = new String(chars);
        anagramGroups.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
    }
    return new ArrayList<>(anagramGroups.values());
}
                        

Examples:

// Example 1
System.out.println(groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"}));
// Output: [[eat, tea, ate], [tan, nat], [bat]]
// Example 2
System.out.println(groupAnagrams(new String[]{""}));
// Output: [[""]]
// Example 3
System.out.println(groupAnagrams(new String[]{"a"}));
// Output: [[a]]

Time & Space Complexity:

Time Complexity: O(n * k log k) where n is the number of strings and k is the maximum length of any string
Space Complexity: O(n * k) to store all the strings in the result

Practice Challenge

Now that you've learned about hash tables for frequency counting and grouping, try these practice challenges to reinforce your understanding.

Challenge 1: Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

Requirements:

You may assume that each input has exactly one solution
You may not use the same element twice
Your solution should have a time complexity better than O(n²)

                            /**
 * @param nums
 * @param target
 * @return indices of the two numbers such that they add up to target
 */
public static int[] twoSum(int[] nums, int target) {
    // Your code here
    return new int[]{};
}
                        

Examples:

// Example 1
twoSum([2, 7, 11, 15], 9)
// Output: [0, 1] (because nums[0] + nums[1] = 2 + 7 = 9)

// Example 2
twoSum([3, 2, 4], 6)
// Output: [1, 2]

// Example 3
twoSum([3, 3], 6)
// Output: [0, 1]

Challenge 2: Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Requirements:

An anagram is a word formed by rearranging the letters of another word
All inputs consist of lowercase English letters

                            /**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isAnagram(s, t) {
    // Your code here
}
                        

Additional Resources:

If you want more practice with hash tables, check out these LeetCode problems: