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

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

1paragraph

#### Two Sum

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

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

6paragraph

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
7list
``` 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```
8code

### Find the duplicates in the array

``` 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```