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
- 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) —
loading...
Last Post: Algorithms to Compute the Interleaved Linked List
Next Post: Linked List Intersection Algorithm