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

0heading

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

2subheading
For a given sorted array [2,7,11,15] find the two numbers such that the sum is equal to the target 9..
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

9heading
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number..
11image
  • 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.
12list
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
13code