Promoted

Promoted

## Solving array problems with two pointers

Topic: Algorithms

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 | 0 | heading |

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 | 1 | paragraph |

## Two Sum | 2 | subheading |

3 | image | |

```
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)
``` | 4 | code |

167. Two Sum II - Input array is sorted | 5 | link |

But we use two pointers that can be done in linear time O(n). | 6 | paragraph |

Promoted Promoted - 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
| 7 | list |

```
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
else:
return [start+1,end+1] #condition satisfied
return -1
``` | 8 | code |

## Find the duplicates in the array | 9 | heading |

10 | link | |

11 | image | |

- 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[0].
- 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.
| 12 | list |

```
def findDuplicate(nums):
n = len(nums)
if n > 1:
slow = nums[0]
fast = nums[slow]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
fast = 0
while fast != slow:
fast = nums[fast]
slow = nums[slow]
return slow
return -1
``` | 13 | code |

Related Posts