Intro to Two Pointers Algorithm

Two pointers algorithm is frequently used in solving array/list problems. One classic example is the Two Sum problem. In this post, let’s solve some two pointers problems together.

Level 1: Two Sum

Description:

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.
  • If the sum is less than the target, meaning that the left pointer needs to be increased to meet the target sum, we move the left pointer to its right
  • If the sum is greater than the target, meaning that the right pointer needs to be decreased to meet the target sum, we move the right pointer to its left
Input: numbers = [2,7,11,15], target = 9Initial pointers:        [2, 7, 11, 15]
^ ^
| |
left right
left+right=17>target, we move right pointer to create a smaller sum
1st move of the right pointer:
[2, 7, 11, 15]
^ ^
| |
left right
left+right=13>target, we move right pointer to create a smaller sum
2nd move of the right pointer:
[2, 7, 11, 15]
^ ^
| |
left right
left+right=13=target, find the result
def twoSum(self, numbers: List[int], target: int) -> List[int]:    left = 1
right = len(numbers)

while left < right:
curr = numbers[left - 1] + numbers[right - 1]
if curr == target:
return [left, right]
elif curr < target:
left += 1
else:
right -= 1

return -1

Level 2: Three Sum

Description:

Input:[-1,0,1,2,-1,-4]
Output: [[-1, 0, 1],[-1, -1, 2]]
Input: numbers = [-1,0,1,2,-1,-4], target = 9Sort the input array, we get: [-4,-1,-1,0,1,2]Initially:
We set a = -4, we need to find two numbers that add up to 4 in the remaining array.
[-4,-1,-1,0,1,2]
^ ^ ^
| | |
a b c
Now b + c = 1 < 4, we move b to its right.
When a = -4, 1st move:
[-4,-1,-1,0,1,2]
^ ^ ^
| | |
a b c
Now b + c = 1 < 4, we move b to its right.
When a = -4, 2nd move:
[-4,-1,-1,0,1,2]
^ ^ ^
| | |
a b c
Now b + c = 2 < 4, we move b to its right.
When a = -4, 3rd move:
[-4,-1,-1,0,1,2]
^ ^ ^
| | |
a b c
Now b + c = 3 < 4, we can't find a combination of b and c that's add up to 4, we move a to it's right.
When a = -1, initially:
[-4,-1,-1,0,1,2]
^ ^ ^
| | |
a b c
Now b + c = 2 > 1, we move c to its left.
When a = -1, 1st move:
[-4,-1,-1,0,1,2]
^ ^ ^
| | |
a b c
Now b + c = 1, we find one tuple: [-1, 0, 1]
....Contine till we iterate the whole array.

def threeSum(nums):
nums = sorted(nums)
results = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
find_two_sum(nums, i + 1, len(nums) - 1, -nums[i], results)

return results

def find_two_sum(nums, left, right, target, results):
last_pair = None
while left < right:
if nums[left] + nums[right] == target:
if (nums[left], nums[right]) != last_pair:
results.append([-target, nums[left], nums[right]])
last_pair = (nums[left], nums[right])
right -= 1
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else:
left += 1

on the way to become a programmer