# Solution for interview question: Two Sum

## 1. Understanding the Problem

- You are given an array of integers and a target sum.
- The task is to find two distinct numbers in the array that add up to the target.
- You should return their indices as a result.

## 2. Brute Force Approach (Inefficient)

- Start by considering a brute force approach where you check every possible pair.
- For each number, iterate through the remaining numbers and check if they add up to the target.
- This approach has O(n²) time complexity.

## 3. Identifying the Core Operation

- The core operation is checking whether two numbers in the array add up to the target.
- For each number
`num`

, check if there’s another number`complement`

such that:`num + complement = target`

- The complement can be calculated as
`complement = target - num`

.

## 4. Using a Hash Map for Efficient Lookup

- Searching through the array takes O(n) time if done linearly. To make this faster, you can use a hash map (dictionary).
- A hash map allows for constant-time lookups (O(1)), so you can check if the complement exists as you iterate through the array.

## 5. Initializing the Hash Map

- Create an empty hash map to store numbers and their indices as you iterate through the array.

## 6. Iterate Through the Array and Calculate Complement

- Loop through the array.
- For each number, calculate its complement (the difference between the target and the current number).
- The complement is calculated as
`target - num`

.

## 7. Check if the Complement Exists in the Hash Map

- For each number, check if the complement exists in the hash map.
- If the complement is already in the hash map, it means you’ve found two numbers that add up to the target.
- Return the indices of the current number and its complement.

## 8. Store the Current Number in the Hash Map

- If the complement is not found in the hash map, store the current number and its index in the hash map.
- This ensures that it can be checked as a complement for future numbers.

## 9. Handle Edge Cases

- Ensure that the input array has at least two numbers.
- Return
`None`

if no solution is found.