Teaching Kids Programming – Two Sum Algorithms


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it’s best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value – x
where value is the input parameter. Can we change our array somehow so that this search becomes faster?
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Bruteforce Algorithm to Find Two Sum Indices

We can bruteforce the indice pairs and that will take O(N^2) quadratic time. This will only work when N is relatively small.

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[i] + nums[j] == target:
                    return [j, i]
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[i] + nums[j] == target:
                    return [j, i]

Linear Algorithm of Two Sum via Hash Map

We can reduce the complexity by using a hash map to remember the indices of the numbers that we have seen so far.

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        data = defaultdict(int)  # or data = {}
        for i,v in enumerate(nums):
            if target - v in data:
                return [data[target-v],i]
            data[v] = i
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        data = defaultdict(int)  # or data = {}
        for i,v in enumerate(nums):
            if target - v in data:
                return [data[target-v],i]
            data[v] = i

Then, for each current number, we are looking for the difference between it and the target number. And return the indice immediately as sooon as we find it appearing in the hash table.

See also: The Two Sum Algorithm using HashMap in C++/Java

When array is sorted, we can use two pointer algorithm or binary search: Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted

Two Sum Variation Problems

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
604 words
Last Post: Algorithms to Compute the Interleaved Linked List
Next Post: Linked List Intersection Algorithm

The Permanent URL is: Teaching Kids Programming – Two Sum Algorithms

Leave a Reply