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 {string} str - Input string
 * @returns {string|null} - First non-repeating character or null
 */
function firstNonRepeatingChar(str) {
    // Create frequency map
    const charCount = new Map();
    
    // First pass: count frequencies
    for (const char of str) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    // Second pass: find first char with count 1
    for (const char of str) {
        if (charCount.get(char) === 1) {
            return char;
        }
    }
    
    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 {string[]} strs - Array of strings
 * @returns {string[][]} - Groups of anagrams
 */
function groupAnagrams(strs) {
    const anagramGroups = new Map();
    
    for (const str of strs) {
        // Sort characters to get a unique key for each anagram group
        const sortedStr = str.split('').sort().join('');
        
        // Create or add to an existing group
        if (!anagramGroups.has(sortedStr)) {
            anagramGroups.set(sortedStr, []);
        }
        
        anagramGroups.get(sortedStr).push(str);
    }
    
    // Return the groups as an array of arrays
    return Array.from(anagramGroups.values());
}
                        

Examples:

// Example 1
groupAnagrams(["eat","tea","tan","ate","nat","bat"])
// Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

// Example 2
groupAnagrams([""])
// Output: [[""]]

// Example 3
groupAnagrams(["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 {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
    // Your code here
}
                        

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: