Leetcode Easy: Two Sum

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, and 7 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.