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

                            def first_non_repeating_char(s):
    # Create frequency map
    char_count = {}
    # First pass: count frequencies
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    # Second pass: find first char with count 1
    for char in s:
        if char_count[char] == 1:
            return char
    return None
                        

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

                            def group_anagrams(strs):
    from collections import defaultdict
    anagram_groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        anagram_groups[key].append(s)
    return list(anagram_groups.values())
                        

Examples:

# Example 1
print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

# Example 2
print(group_anagrams([""]))
# Output: [[""]]

# Example 3
print(group_anagrams(["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²)

                            def two_sum(nums, target):
    # Your code here
    pass
                        

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

                            def is_anagram(s, t):
    # Your code here
    pass
                        

Additional Resources:

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