Solving the LeetCode Two Sum Problem

Problem Overview

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)

Approach 1: Brute Force (Naive Solution)

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

Steps:

1. Iterate through each element nums[i].
2. For each i, iterate through the rest of the elements nums[j] (where j > i).
3. If nums[i] + nums[j] == target, return [i, j].

Code (Python):

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]

Approach 2: Optimal Solution Using Hash Map

• Idea: Use a dictionary to store numbers and their indices as we traverse the array. For each number, check if its complement (target - num) exists in the dictionary.
• Time Complexity: $O(n)$ (single pass through the array)
• Space Complexity: $O(n)$ (to store the dictionary)

Steps:

1. Initialize an empty dictionary num_map.
2. For each index i and value num in nums:
   • Calculate the complement: complement = target - num.
   • If complement exists in num_map, return [num_map[complement], i].
   • Otherwise, store num with its index i in num_map.

Code (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

Example Walkthrough (Using Hash Map)

For nums = [2, 7, 11, 15], target = 9:

1. i=0, num=2 → complement=7 (not in map) → store {2:0}
2. i=1, num=7 → complement=2 (found in map at index 0) → return [0, 1]

Edge Cases to Consider

• Duplicate numbers: The hash map approach handles duplicates correctly because it checks for the complement before adding the current number.
• No solution: The problem states there is exactly one solution, so no need to handle no-solution cases.
• Negative numbers and zero: The solution works for all integers.

Follow-Up Questions

1. Would you like me to explain how to handle cases where there are multiple solutions (if the problem allowed it)?
2. Are you interested in variations of this problem, such as the "Two Sum II" (sorted input) or "Three Sum"?
3. Do you want to see the solution implemented in another programming language (e.g., Java, C++)?
4. Should we discuss the trade-offs between time and space complexity for these approaches?