Solving the Two Sum Problem

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. You may assume that each input has exactly one solution, and you may not use the same element twice.

Example:

• Input: nums = [2,7,11,15], target = 9
• Output: [0,1] (since nums[0] + nums[1] = 2 + 7 = 9)

---

Approaches

1. Brute Force Approach

• Check every possible pair of numbers in the array.
• Time Complexity: $O(n^2)$ (nested loops)
• Space Complexity: $O(1)$ (no extra space used)

Algorithm:

For each index i from 0 to n-1:
    For each index j from i+1 to n-1:
        If nums[i] + nums[j] == target:
            Return [i, j]

2. Optimal Approach Using Hash Map

• Use a hash map (dictionary) to store numbers and their indices as we traverse the array.
• For each number, compute the complement (target - current number).
• If the complement exists in the hash map, return the current index and the complement's index.
• Time Complexity: $O(n)$ (single pass)
• Space Complexity: $O(n)$ (for storing numbers in the hash map)

Algorithm:

Initialize an empty dictionary (hash map)
For index i from 0 to n-1:
    complement = target - nums[i]
    If complement exists in the dictionary:
        Return [dictionary[complement], i]
    Else:
        Store nums[i] with index i in the dictionary

---

Code Implementation (Python)

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
    return []  # Though problem states exactly one solution exists

Explanation:

• We iterate through the list while storing each number and its index in num_map.
• For each number, we check if its complement (target - num) already exists in num_map.
• If found, we return the indices immediately.

---

Edge Cases and Considerations

• Duplicate Numbers: The hash map approach handles duplicates correctly because we check for the complement before adding the current number to the map.
• Negative Numbers: The solution works regardless of sign since complement calculation is algebraic.
• No Solution: The problem states there is exactly one solution, so we don't need to handle no-solution cases.

---

Testing the Solution

Test with the provided example:

• nums = [2,7,11,15], target = 9
  • i=0: num=2, complement=7 (not in map) → store {2:0}
  • i=1: num=7, complement=2 (found in map) → return [0,1]

---

Complexity Analysis

• Time: $O(n)$ — We traverse the list once.
• Space: $O(n)$ — In the worst case, we store all n elements in the hash map.

---

Follow-Up Questions

1. Would you like me to explain how to handle variations of this problem, such as when the input array is sorted?
2. Are you interested in optimizing the solution for memory usage in constrained environments?
3. Shall we explore how to extend this to the "Three Sum" or "Four Sum" problems?