Two Sum

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]

  Constraints:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

  Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

## Two Sum Problem

This problem asks us to find two numbers in an array that add up to a specific target value. Let's explore a couple of approaches.

### 1. Brute Force Approach

The most straightforward solution is to iterate through each element of the array and check its sum with every other element. If we find a pair that adds up to the target, we return their indices.

```python
def twoSum_brute_force(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None  # No solution found

# Example Usage
nums = [2, 7, 11, 15]
target = 9
result = twoSum_brute_force(nums, target)
print(result)  # Output: [0, 1]

2. Optimal Solution: Using a Hash Map

A more efficient approach involves using a hash map (dictionary in Python). We iterate through the array, and for each number, we check if the complement (target - number) exists in the hash map. If it does, we have found our pair. If not, we add the number and its index to the hash map.

def twoSum_optimal(nums, target):
    num_map = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], index]
        num_map[num] = index
    return None  # No solution found

# Example Usage
nums = [2, 7, 11, 15]
target = 9
result = twoSum_optimal(nums, target)
print(result)  # Output: [0, 1]

3. Big(O) Run-time Analysis

• Brute Force: The brute-force approach has a time complexity of O(n^2) because it involves nested loops, where 'n' is the number of elements in the array.
• Optimal (Hash Map): The optimal approach has a time complexity of O(n) because, in the worst case, we iterate through the array once. Hash map lookups (checking if the complement exists) take O(1) time on average.

4. Big(O) Space Usage Analysis

• Brute Force: The brute-force approach has a space complexity of O(1) because it uses a constant amount of extra space.
• Optimal (Hash Map): The optimal approach has a space complexity of O(n) because, in the worst case, we might store all the elements of the array in the hash map.

5. Edge Cases and Handling

1. No Solution:
   • If no two numbers add up to the target, the function should return None (or raise an exception, depending on the specific requirements).
2. Duplicate Numbers:
   • If the input array contains duplicate numbers, the hash map approach will still work correctly. The algorithm finds any two numbers that add up to the target. If the question specifies something different for duplicate numbers, it has to be handled in the algorithm.
3. Empty Array:
   • If the input array is empty, you can either return an empty array or raise an exception.
4. Large Input:
   • For very large input arrays, the hash map approach is preferable due to its O(n) time complexity.
5. Negative Numbers and Zero:
   • The solution should correctly handle negative numbers and zero values in the input array.

Here's the code including some error handling for edge cases:

def twoSum_optimal_with_edge_cases(nums, target):
    if not nums:
        return None  # Handle empty array case

    num_map = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], index]
        num_map[num] = index

    return None  # No solution found