Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Binary Search Two Sum Algorithm
We can iterate the first number in O(N) and binary search the target-num[i] in O(logN) therefore the overall complexity is O(NLogN).
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
def binary_search(n):
i, j = 0, len(numbers) - 1
while i <= j:
mid = (i + j) // 2
if numbers[mid] == n:
return mid
if n < numbers[mid]:
j = mid - 1
else:
i = mid + 1
return -1
for i in range(len(numbers)):
x = binary_search(target - numbers[i])
if x >= 0 and x != i:
return [min(i + 1, x + 1), max(i + 1, x + 1)]
We can pass in the range to binary search which is getting smaller and smaller after we determine the first number.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
def binary_search(i, j, n):
while i <= j:
mid = (i + j) // 2
if numbers[mid] == n:
return mid
if n < numbers[mid]:
j = mid - 1
else:
i = mid + 1
return -1
for i in range(len(numbers)):
x = binary_search(i + 1, len(numbers) - 1, target - numbers[i])
if x >= 0: # we don't need to check if it is same as numbers[i]
return [min(i + 1, x + 1), max(i + 1, x + 1)]
Two Pointer Two Sum Algorithm
Since the array is sorted, we can apply two pointer algorithm. The two pointers are initialised to be two ends, and we compare sum with target and moving lower pointer to the right if the sum is lower, and moving the upper pointer to the left if the sum if bigger, until they meet in the middle.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i, j = 0, len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
elif numbers[i] + numbers[j] < target:
i += 1
else:
j -= 1
The time complexity is O(N) and the space complexity is O(1) constant.
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) —
Last Post: Fast and Slow Pointer to Get the Middle of the Linked List
Next Post: Counting the Only Child in the Binary Tree using Breadth First Search Algorithm
