Challenge: Target Sum

Question:

Find two indexes from a list whose values are summed up to a predefined target number.

  • Input: A list of integers and a target number.
  • Output: another list containing two (or a pair of) indexes of the input list whose values summed up to the target number. If such pair does not exist, return None. If there exists many such pairs, output one of them.

An example:

  • Input
    • array: [2, 0, 1, 6, 8, 9]
    • target number: 7
  • Output: [2, 3]
  • Explanation: The two numbers that summed up to 7 are 1 and 6 and they are the second and the third element of the array input.

Answer

A brute force solution with O(n2) complexity:

def target_sum(arr_int, target):
  for i in range(len(arr_int)):
    for j in range(i+1, len(arr_int)):
      if arr_int[i]+arr_int[j] == target:
        # found, return the index pair
        return [i,j]
  # if not found
  return None

A faster solution with O(n) complexity, using a hash map:

def faster_target_sum(arr_int, target):
  remainders = {}
  for i in range(len(arr_int)):
    if arr_int[i] in remainders:
      # found, return the index pair
      return [remainders[arr_int[i]], i]
    else:
      # not found yet, added the remainder to the hash map
      remainder = target - arr_int[i]
      remainders[remainder] = i
  # if not found 
  return None

👍 Have fun while coding with Python!

👌 Please subscribe to receive notifications on future challenges.

💬 If you have any questions simply write a comment down below.

Leave a Comment