Two Sum Problem

May 26, 2024

Lecture on solving a popular LeetCode Problem

Problem Statement

  • Given an input array and a target sum, find two values in the array that sum to the target.
  • Return the indices of these two values.
  • Example: Input array = [2, 7, 1, 5, 3], target = 9 => Output = [0, 1] (indices of 2 and 7).
  • Assumptions:
    • There is exactly one solution.
    • No need to consider multiple or no solutions.

Brute Force Solution

  • Approach:

    • Check every combination of two values.
    • Examine if they sum to the target.
    • Process: For each element, check it with every possible combination with the remaining elements.
  • **Example:

    • Start with 2:
      • Check 2 with remaining elements 1, 5, 3, none sum to 9.
    • Move to 1:
      • Check 1 with 5 and 3.
      • 1 + 3 = 4 (find the pair that sums up to the target).
  • Complexity:

    • Time Complexity: O(n^2).

Optimized Solution Using Hash Map

  • **Concept:

    • Utilize a hash map to store elements and their indices.
    • Check if the complement of the current element exists in the hash map.
  • **Steps:

    • Initialize an empty hash map.
    • Iterate through the array:
      1. For current element x, calculate the complement needed to reach the target: complement = target - x.
      2. Check if complement exists in the hash map.
      3. If it exists, return the indices of complement and x.
      4. Otherwise, add x to the hash map.
  • **Algorithm:

    1. Initialize an empty hash map. (Python: previousMap = {})
    2. Iterate over the array elements (need both index i and actual value n):
      for i, n in enumerate(array):
          complement = target - n
          if complement in previousMap:
              return [previousMap[complement], i]
          previousMap[n] = i
      
    3. If a solution exists, it will be found during iteration.
    4. No need for special return cases as one solution is guaranteed.
  • **Complexity:

    • Time Complexity: O(n) (due to single pass and constant time lookup/add operations).
    • Space Complexity: O(n) (for storing elements in hash map).

Implementation in Python

array = [2, 7, 1, 5, 3]
target = 9

previousMap = {}
for i, n in enumerate(array):
    complement = target - n
    if complement in previousMap:
        print([previousMap[complement], i])  # Output the result
    previousMap[n] = i
  • Code will find the solution and print indices of values that sum to the target.