Teaching Kids Programming – 3 Different Approaches to Solve Two-Sum Problem

Teaching Kids Programming: Videos on Data Structures and Algorithms

This is actually a very famous known problem for beginners to into Algorithms & Data Structures. Given a list of numbers, and a target, find out if there are two numbers in the list that sums up to the target.

For example: nums = [2, 1, 4, 6, 7], and target is 10 – we should return True as the 4+6 = 10.

Two Sum in Bruteforce Algorithm

We can bruteforce each possible pairs (j < i) and and check if nums[i] + nums[j] is the target. The complexity is O(N^2).

1
2
3
4
5
6

def twoSums(nums, target):
  for i in range(len(nums)):
    for j in range(i):
      if nums[i] + nums[j] == target:
        return True
  return False

def twoSums(nums, target):
  for i in range(len(nums)):
    for j in range(i):
      if nums[i] + nums[j] == target:
        return True
  return False

As you can imagine, this approach is inefficient and you may likely to get Time Limit Exceeded verdict when the nums contain a huge number of elements.

Using a Hash Table to Solve Two Sum Problem

We can remember the numbers that we’ve seen using a Hash Table (Hash Set). In Python, we can use a dictionary {} or a set()

1
2
3
4
5
6
7

def twoSums(nums, target):
   nb = {} # or nb = set()
   for i in nums:
      if target - i in nb:
         return True
      nb[i] = True # or nb.add(i)
   return False

def twoSums(nums, target):
   nb = {} # or nb = set()
   for i in nums:
      if target - i in nb:
         return True
      nb[i] = True # or nb.add(i)
   return False

Here, we only need to visit the array once thus the complexity is O(N). We use a hash set (or dictionary), and thus the space complexity is O(N).

Two Sum by Sorting and Two Pointer Algorithm

We can sort the array, and then apply the two-pointer algorithm.

1
2
3
4
5
6
7
8
9
10
11

def twoSums(nums, target):
  nums.sort()
  left, right = 0, len(nums) - 1
  while left < right:
    if nums[left] + nums[right] == target:
      return True
    if nums[left] + nums[right] < target:
      left += 1
    else:
      right -= 1
  return False

def twoSums(nums, target):
  nums.sort()
  left, right = 0, len(nums) - 1
  while left < right:
    if nums[left] + nums[right] == target:
      return True
    if nums[left] + nums[right] < target:
      left += 1
    else:
      right -= 1
  return False

As long as the left and right pointer not meeting in the middle, we move the left pointer one step to the right if the sum is less than the target, or the right pointer one step to the left if the sum is larger. Otherwise, when the sum equals to the target, we can just return True.

The overall complexity is O(NLogN) as the sorting dominates the O(N) two pointers.

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —