Problem Definition:
Given an array of integers
nums
and an integer target
, return indices of the two numbers such that they add up to target
.You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6 Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6 Output: [0,1]
Solution:
Approach:
We can solve this using a hash map (dictionary) for optimal performance (O(n) time complexity), as this allows us to look up complements in constant time.
- As we iterate through the array, for each number
num
, we calculate the complement (target - num
).
- If the complement exists in our hash map, we've found the two numbers, so we return their indices.
- If not, we store the current number and its index in the hash map and continue.
Python Code:
def twoSum(nums, target): # To store the number and its index hash_map = {} for i, num in enumerate(nums): complement = target - num # Find the complement if complement in hash_map: # If complement exists, return its index and the current index return [hash_map[complement], i] # Otherwise, store the current number and index in the hash map hash_map[num] = i # If no solution, return an empty list return []
Explanation:
- Initialize a hash map:
hash_map = {}
: This will store the numbers we've seen so far as keys, with their indices as values.
- Iterate over the array:
- For each number in the array (
num
), we calculate the complement (target - num
). - If the complement exists in the hash map, that means we already encountered the number that, when added to
num
, equals the target. We return the index of the complement and the current index. - Otherwise, we store
num
and its index in the hash map.
- Return the indices:
- When the complement is found, we return the indices of the two numbers.
Explaining The Concept Of Hashmap:
A hash map in Python refers to a data structure that stores key-value pairs, where each key is unique, and it allows efficient lookups, insertions, and deletions. The most commonly used hash map in Python is the dictionary (
dict
).Key Concepts of a Hash Map:
- Key-Value Pairs: Data is stored as a pair where each key is associated with a corresponding value.
- Hashing: Keys are hashed to generate a unique index in the underlying array where the value is stored.
- Efficiency: Operations like lookup, insert, and delete can be performed in constant time on average, i.e., O(1) complexity.
Python's Dictionary (dict
):
In Python, dictionaries are implemented as hash maps. You use keys to store and retrieve values. Here's a basic example:
Creating a Dictionary:
# Creating an empty dictionary my_dict = {} # Adding key-value pairs to the dictionary my_dict['apple'] = 5 my_dict['banana'] = 3 my_dict['orange'] = 7 print(my_dict) # Output: {'apple': 5, 'banana': 3, 'orange': 7}
In this example:
'apple'
,'banana'
, and'orange'
are keys.
5
,3
, and7
are their associated values.
Accessing Values by Key
# Accessing value associated with the key 'apple' print(my_dict['apple']) # Output: 5
If the key exists in the hash map, you can retrieve the associated value instantly.
Inserting and Updating Values
# Inserting a new key-value pair my_dict['grape'] = 10 # Updating an existing value my_dict['apple'] = 6 print(my_dict) # Output: {'apple': 6, 'banana': 3, 'orange': 7, 'grape': 10}
Deleting Key-Value Pairs
# Using del to remove a key-value pair del my_dict['banana'] # Using pop to remove a key-value pair and return the value value = my_dict.pop('grape') print(my_dict) # Output: {'apple': 6, 'orange': 7} print(value) # Output: 10
Checking for a Key
if 'apple' in my_dict: print("Apple is in the dictionary")
Hash Maps in Real-World Examples
Example 1: Counting the Occurrences of Items
You can use a hash map (dictionary) to count how many times each item appears in a list.
fruits = ['apple', 'banana', 'orange', 'apple', 'orange', 'apple'] # Create an empty dictionary count_dict = {} # Count the occurrences of each fruit for fruit in fruits: if fruit in count_dict: count_dict[fruit] += 1 else: count_dict[fruit] = 1 print(count_dict) # Output: {'apple': 3, 'banana': 1, 'orange': 2}
Example 2: Using a Hash Map to Solve the Two Sum Problem
As discussed earlier, a hash map can be used to efficiently solve the Two Sum problem by storing the complement of each number and checking for its existence:
def twoSum(nums, target): hash_map = {} # Initialize an empty hash map (dictionary) for i, num in enumerate(nums): complement = target - num if complement in hash_map: return [hash_map[complement], i] # Return indices of the two numbers hash_map[num] = i # Store the number and its index in the hash map # Test the function nums = [2, 7, 11, 15] target = 9 print(twoSum(nums, target)) # Output: [0, 1]
How Hash Maps Work Internally
Internally, a hash function is used to convert each key into a unique index. This index determines where the corresponding value is stored in memory. For example, if you use
'apple'
as a key, Python's hash function will compute a hash value for 'apple'
and store its corresponding value in that location.In case two keys generate the same hash (a "collision"), Python has a strategy (like linked lists or open addressing) to handle it.
Advantages of Hash Maps:
- Fast Access: Average case O(1) time complexity for lookups, insertions, and deletions.
- Flexible: Keys can be of any immutable type (e.g., strings, integers, tuples).
- Readable: Keys provide context for the values stored.
Limitations:
- No Ordering: In Python versions before 3.7, dictionaries didn’t preserve insertion order. In Python 3.7+, insertion order is preserved, but it's not guaranteed in every language's hash maps.
- Hash Collisions: If many keys hash to the same index, performance degrades to O(n).
Conclusion:
Hash maps (dictionaries in Python) are extremely useful for storing key-value pairs and are highly efficient for lookups, inserts, and deletes. They're widely used in various algorithms and data-processing tasks due to their speed and flexibility.