Theory Overview

• Arrays, sets, and maps are all implementations of hash tables
• Hash tables excel at determining whether an element has been encountered previously

Problem 1: Valid Anagram

• Problem Link: 242. Valid Anagram - LeetCode
• Difficulty: Easy
• Solution Approach: When the chaarcter range is small, arrays can serve as hash tables

• Create an array of length 26 with all zeros
• First, iterate through characters in string s, incrementing the count at the corresponding index
  • Calculate relative position using ASCII values: each letter's ASCII minus 'a' ASCII gives index 0-25
• Then, iterate through cahracters in string t as indices, decrementing counts where matches occur
• Check if all stored values equal zero; if so, return true

class Solution:
    def isValidAnagram(self, first_string: str, second_string: str) -> bool:
        counter_array = [0] * 26
        
        for char in first_string:
            # No need to memorize ASCII of 'a', just calculate relative position
            counter_array[ord(char) - ord("a")] += 1
            
        for char in second_string:
            counter_array[ord(char) - ord("a")] -= 1
        
        for count in counter_array:
            if count != 0:
                # If any element in counter_array is non-zero, strings differ in character frequency
                return False
        return True

Problem 2: Intersection of Two Arrays

• Problem Link: 349. Interseciton of Two Arrays - LeetCode
• Difficulty: Easy
• Solution Approach: Using hash sets

Method One: Hash Map

class Solution:
    def findIntersection(self, array_one: List[int], array_two: List[int]) -> List[int]:
        # Store elements from first array in hash map
        storage_map = {}
        for num in array_one:
            storage_map[num] = storage_map.get(num, 0) + 1
        
        # Use set to store results
        result_set = set()
        for num in array_two:
            if num in storage_map:
                result_set.add(num)
                del storage_map[num]
        
        return list(result_set)

Method Two: Array-based Counting

class Solution:
    def findIntersection(self, array_one: List[int], array_two: List[int]) -> List[int]:
        first_counter = [0] * 1001
        second_counter = [0] * 1001
        output_result = []
        
        for val in array_one:
            first_counter[val] += 1
        for val in array_two:
            second_counter[val] += 1
        
        for idx in range(1001):
            if first_counter[idx] * second_counter[idx] > 0:
                output_result.append(idx)
        
        return output_result

Problem 3: Happy Number

• Problem Link: 202. Happy Number - LeetCode
• Difficulty: Easy
• Solution Approach: Detect cycles using hash structures

Method One: Using Set

class Solution:
    def checkHappyNumber(self, number: int) -> bool:        
        seen_values = set()

        while True:
            number = self.computeSquareSum(number)
            if number == 1:
                return True
            
            # If intermediate result repeats, we're in a loop, not a happy number
            if number in seen_values:
                return False
            else:
                seen_values.add(number)

    def computeSquareSum(self, num: int) -> int: 
        squared_total = 0
        while num:
            num, digit = divmod(num, 10)
            squared_total += digit ** 2
        return squared_total

Method Two: Using List

class Solution:
   def checkHappyNumber(self, number: int) -> bool:
       history_list = []
       while number not in history_list:
           history_list.append(number)
           current_sum = 0
           num_str = str(number)
           for digit_char in num_str:
               current_sum += int(digit_char) ** 2
           if current_sum == 1: 
               return True
           else: 
               number = current_sum
       return False

Method Three: Floyd's Cycle Detection

class Solution:
   def checkHappyNumber(self, number: int) -> bool:        
       slow_ptr = number
       fast_ptr = number
       while self.computeSquareSum(fast_ptr) != 1 and self.computeSquareSum(self.computeSquareSum(fast_ptr)):
           slow_ptr = self.computeSquareSum(slow_ptr)
           fast_ptr = self.computeSquareSum(self.computeSquareSum(fast_ptr))
           if slow_ptr == fast_ptr:
               return False
       return True
   
   def computeSquareSum(self, num: int) -> int: 
       squared_total = 0
       while num:
           num, digit = divmod(num, 10)
           squared_total += digit ** 2
       return squared_total

Problem 4: Two Sum

• Problem Link: 1. Two Sum - LeetCode
• Difficulty: Easy
• Solution Approach: Hash map for efficient lookup

Method One: Hash Map

class Solution:
    def findTwoSum(self, numbers: List[int], target_sum: int) -> List[int]:
        lookup_table = dict()

        for index, value in enumerate(numbers):  
            complement = target_sum - value
            if complement in lookup_table:   # Check current element and search for matching pair in map
                return [lookup_table[complement], index]
            lookup_table[value] = index    # If no match found, add visited element and its index to map
        return []

Method Two: Brute Force

class Solution:
    def findTwoSum(self, numbers: List[int], target_sum: int) -> List[int]:
        for outer_idx in range(len(numbers)):
            for inner_idx in range(outer_idx + 1, len(numbers)):
                if numbers[outer_idx] + numbers[inner_idx] == target_sum:
                    return [outer_idx, inner_idx]