Overview

Hashmaps are dynamic data structures that efficiently store and manage key-value pairs using a technique called hashing. In a hashmap, each key is processed through a hash function, which generates a unique address in memory for storing its corresponding value. This allows for constant O(n) access to elements, regardless of the size of the data set, making hashmaps ideal for applications that require rapid lookup, insertion, and deletion operations.

When To Use

Identifying the need to use a hashmap is essential when you encounter problems that require efficient mappings of key-value pairs. Hashmaps excel in tasks such as counting frequencies, like determining the number of occurrences of each character in a string. Or grouping items by attributes, such as classifying words by their starting letter. Additionally, hashmaps are invaluable for quickly finding pairs that satisfy certain conditions, such as two numbers that add up to a specific target in a list, by storing and checking for the necessary complements efficiently. This capability significantly speeds up solutions

Now Let’s go through this Example Problem: Two Sum

Problem: Two Sum

We are given an array of integers nums and an integer target. The goal is to return the indices of two numbers in the array such that they add up to the target. Each input has exactly one solution, and you cannot use the same element twice. The order of the indices does not matter.

Brainstorming the Approach

1. Brute Force Approach:
   • The simplest approach is to try all pairs of numbers in the array. For each number i, we can check every other number j to see if nums[i] + nums[j] == target.
   • While this approach works, it has a time complexity of O(N^2) because we need to check each pair, which can be inefficient for large arrays.
2. Optimized Approach Using a Hash Map:
   • We can optimize this solution using a hash map (dictionary in Python).
   • As we iterate through the array, we can store the complement of the current number (i.e., target - nums[i]) in a hash map. The complement is the number we need to find in the array to add up to the target with the current number.
   • As we process each element, we check if it already exists in the hash map. If it does, we have found the pair that adds up to the target. Otherwise, we add the current number and its index to the hash map for future reference.
   • This approach reduces the time complexity to O(N) because we only need to iterate through the array once and lookups in the hash map are O(1).
3. Key Observations:
   • Each element will be processed only once.
   • We store the index of each element as we iterate through the array, which allows us to easily return the correct indices when we find the matching pair.
   • We need to be careful not to reuse the same element twice, which is handled by ensuring that we only look for pairs using elements that come before the current element.
4. Edge Cases:
   • Arrays with duplicate numbers (e.g., [3, 3]).
   • Arrays with only two numbers (e.g., [1, 2] and target = 3).
   • Arrays where all elements are the same (e.g., [2, 2, 2, 2]).

Pseudocode

• Initialize an empty hash map num_to_index to store the complement of the numbers we have seen.
• Loop through the array nums with an index i:
  • Calculate the complement of the current number: complement = target - nums[i].
  • If complement is already in num_to_index, return the indices [num_to_index[complement], i] since we found the pair.
  • Otherwise, store the current number and its index in the hash map: num_to_index[nums[i]] = i.

Code Implementation

class Solution(object):
	def twoSum(self, nums, target):
	    num_to_index = {}

	    for i, num in enumerate(nums):
	        complement = target - num

	        if complement in num_to_index:
	            return [num_to_index[complement], i]

	        num_to_index[num] = i

Explanation of the Code

1. Initialization:
   • We initialize an empty dictionary num_to_index to store numbers and their corresponding indices as we iterate through the array.
2. Main Loop:
   • For each number num at index i in the array nums, we calculate its complement as target - num.
   • We then check if this complement already exists in the dictionary num_to_index.
     • If it exists, it means we've found two numbers that add up to the target, so we return their indices: [num_to_index[complement], i].
   • If the complement does not exist in the dictionary, we store the current number num and its index i in num_to_index.