### 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

*, and you may not use the***exactly one solution***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.