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.