I'll help you solve the Two Sum problem from LeetCode. Let me break this down step by step.

Problem Understanding

The Two Sum problem asks: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Constraints:

• Each input has exactly one solution
• You may not use the same element twice
• Return the answer in any order

Approaches

1. Brute Force Approach (O(n²) time, O(1) space)

def twoSum(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]

Time Complexity: $O(n^2)$ Space Complexity: $O(1)$

2. Hash Map Approach (O(n) time, O(n) space) - Optimal

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

Time Complexity: $O(n)$ Space Complexity: $O(n)$

Step-by-Step Example

Let's use nums = [2, 7, 11, 15] and target = 9:

Edge Cases to Consider

• Negative numbers: nums = [-1, -2, -3, -4, -5], target = -8
• Zero as target: nums = [0, 4, 3, 0], target = 0
• Duplicate numbers: nums = [3, 3], target = 6

Complete Solution

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    num_dict = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_dict:
            return [num_dict[complement], index]
        num_dict[num] = index
    return []  # Though problem states exactly one solution exists

Why This Works

The hash map approach works because:

1. We store each number and its index as we iterate
2. For each number, we calculate what complement would make the target
3. If we've already seen the complement, we have our solution
4. This ensures we only traverse the array once

Time Complexity: $O(n)$ - Single pass through the array Space Complexity: $O(n)$ - Worst case we store all elements

Would you like me to:

• Explain how to handle specific edge cases in more detail?
• Show variations of this problem (like Three Sum or Four Sum)?
• Provide test cases to verify your implementation?
• Discuss the mathematical reasoning behind why this approach is optimal?