Two-pointers is a pretty common method to solve array problems in linear time with constant space. Two-pointers problems can be solved by traversing an array by either fast and slow pointers or by left and right pointers. Two-pointers problems can be used for sliding window problems. We can adjust window size sliding left or right pointers. Let's see some examples to get a clear idea of two problems.
When there is comparison of two numbers in an array
If there requires a comparison between two numbers in an array it will require O(n^2) brute force. This is because we will have to run two loops for comparing each number with another number. Look at following
If this problem is solved with brute force we require two loops.
for i in numbers:
For j in numbers
If i + j == target:
print(“Target is sum of”, i, j)
But we use two pointers that can be done in linear time O(n).
We need one pointer to start the array and another pointer at the end of the array.
We take the sum of start and end. If the sum is equal to the target we return numbers at the start or end.
If we find the sum is less than the target we need a bigger number this we can find by moving the start pointer by 1.
We compare again if the sum matches target return numbers at start and end. If the sum is larger than the target we need a smaller number.
We can find smaller numbers by moving the end towards the left. We do this repeatedly until the start and end are together. If we did not find we would return -1.
Below is the python code
def twoSum(numbers, target):
start = 0 #point start to left
end = len(numbers)-1 #point end to right. we use len-1 because array index starts with 0
sum = 0 #initial sum with 0
while start != end : #run loop until start and end point to same number
sum = numbers[start] + numbers[end]
if sum > target:
end -= 1 #look for smaller number
elif sum < target:
start +=1 #look for larger number
return [start+1,end+1] #condition satisfied
Find the duplicates in the array
Use two pointers the fast and the slow.
The fast one goes forward two steps each time, while the slow one goes only step each time.
They must meet the same item when slow==fast.
In fact, they meet in a circle, the duplicate number must be the entry point of the circle when visiting the array from nums.
Next we just need to find the entry point. We use a point(we can use the fast one before) to visit form begining with one step each time, do the same job to slow. When fast==slow, they meet at the entry point of the circle.
n = len(nums)
if n > 1:
slow = nums
fast = nums[slow]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
fast = 0
while fast != slow:
fast = nums[fast]
slow = nums[slow]