The Two Sum problem is a classic coding challenge often featured in technical interviews, particularly for roles involving algorithmic problem-solving. It’s a great problem for understanding how to manipulate arrays and use hashmaps (dictionaries in Python) efficiently. In this post, we'll walk through how to solve the Two Sum problem in Python, explaining step by step the logic, approach, and an optimal solution.

Problem Statement

Given an array of integers nums and an integer target, find two numbers in the array that add up to the target and return their indices.

Constraints:

  1. There is exactly one solution.
  2. You cannot use the same element twice.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  # Because nums[0] + nums[1] = 2 + 7 = 9

Steps to Solve the Two Sum Problem

Step 1: Understand the Naive Solution (Brute Force)

The most straightforward approach to solve the problem is to check every possible pair of numbers in the list to see if they sum to the target.

Approach:

  1. Iterate through each element in nums.
  2. For each element, check all subsequent elements to see if their sum equals target.
  3. If a valid pair is found, return their indices.

Python Code:

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Time Complexity:

  • Time Complexity: O(n^2) — Nested loops make this solution inefficient for large input sizes.

Example:

nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

Step 2: Optimize with a Hashmap (Dictionary)

The brute-force solution works but is inefficient because it checks every pair. We can optimize it using a hashmap (dictionary) to achieve linear time complexity.

Optimized Approach:

  1. As you iterate through the list, for each element, calculate the difference between the target and the current number (i.e., target - current_num).
  2. Check if this difference exists in a dictionary.
    • If it does, the pair has been found: return the current index and the index stored in the dictionary.
    • If it doesn’t, store the current number’s index in the dictionary for future reference.

This way, you only need a single pass through the list, significantly improving the time complexity.

Python Code:

def two_sum(nums, target):
    num_map = {}  # Dictionary to store numbers and their indices
    for i, num in enumerate(nums):
        difference = target - num
        if difference in num_map:
            return [num_map[difference], i]
        num_map[num] = i  # Store the number with its index

Explanation:

  • num_map keeps track of the numbers you've seen so far along with their indices.
  • For each number num in nums, calculate target - num (the number you need to form the sum).
  • If that number is already in num_map, return its index along with the current index (i).
  • If not, store the current number and its index in the dictionary for future reference.

Example:

nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

In this example, when the iteration reaches 7, it computes 9 - 7 = 2. Since 2 is already in the dictionary (with index 0), it returns [0, 1].

Time Complexity:

  • Time Complexity: O(n) — Each element is processed only once, making it much faster than the brute-force approach.
  • Space Complexity: O(n) — The dictionary stores up to n elements where n is the size of the input array.

Step 3: Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    nums = [-3, 4, 3, 90]
target = 0
result = two_sum(nums, target)
print(result)  # Output: [0, 2]

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    nums = [3, 3]
target = 6
result = two_sum(nums, target)
print(result)  # Output: [0, 1]

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    nums = [1, 4]
target = 5
result = two_sum(nums, target)
print(result)  # Output: [0, 1]

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    nums = [0, 4, 3, 0]
target = 0
result = two_sum(nums, target)
print(result)  # Output: [0, 3]

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    nums = list(range(100000))
target = 199999
result = two_sum(nums, target)
print(result)  # Output: [99998, 99999]

Conclusion

The Two Sum problem is an excellent example of how using the right data structure (in this case, a hashmap or dictionary) can significantly improve the efficiency of your solution. With the optimized solution, you can solve the problem in linear time, making it scalable even for large input sizes.

Mastering this problem and understanding the underlying principles will prepare you for more complex algorithmic challenges, such as other problems involving hashmaps, arrays, or dynamic programming.