Three Pointers

The three pointers technique involves using three reference variables to iterate through a data structure or range for certain search or transformation tasks.

A common pattern is having left, right, and current pointers.

Java example - Remove duplicates from sorted array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int removeDuplicates(int[] nums) {
  int n = nums.length;
  if (n <= 2) return n;

  int curr = 1, left = 1, right = 1;

  while (right < n) {
    if (nums[curr-1] != nums[right]) {
      nums[left++] = nums[curr++] = nums[right];
    }
    right++;
  }
  return left;
}

C++ example - Partition array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int partition(vector<int>& arr) {  
  int n = arr.size(), pivot = arr[n / 2];
  int i = 0, j = 0, k = n - 1;

  while (j <= k) {
    if (arr[j] < pivot) {
      swap(arr[i++], arr[j++]);
    }
    else if (arr[j] > pivot) {
      swap(arr[j], arr[k--]);
    }
    else {
      j++;
    }
  }
  return i;
}

Python example - Triplet sum:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def threeSum(nums):
  
  nums.sort()
  triplets = []
  for i in range(len(nums)):
    if i > 0 and nums[i] == nums[i-1]:
        continue
    find_triplets(nums, i, triplets)
  return triplets
  
def find_triplets(nums, index, triplets):
    
  left = index + 1
  right = len(nums) - 1
  
  while left < right:
    curr_sum = nums[index] + nums[left] + nums[right]
    if curr_sum == 0:
      # Append triplet 
      left += 1
      right -= 1
    elif curr_sum > 0:
      right -= 1  
    else:
      left += 1

The three pointers approach provides an intuitive way to explore ranges and arrays through relative positioning.

The concept of Three Pointers is often used in algorithm problems, particularly when dealing with arrays or linked lists. It refers to the technique of using three pointers to traverse or manipulate data structures. These pointers might represent different positions in an array or list and can help in solving various problems, like sorting, finding a target element, or other specific requirements.

A common example is when you want to divide an array or list into three parts based on certain conditions. Three pointers are used to mark the division points and traverse the data structure efficiently.

Solution

Let’s demonstrate the Three Pointers technique with a common problem: Sorting an array containing three types of elements (0, 1, and 2). The goal is to sort the array such that all 0’s come first, followed by all 1’s and then all 2’s.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        switch (nums[mid]) {
            case 0:
                swap(nums, low++, mid++);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(nums, mid, high--);
                break;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        switch (nums[mid]) {
            case 0:
                swap(nums[low++], nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(nums[mid], nums[high--]);
                break;
        }
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

These examples demonstrate how to sort an array with three distinct elements using three pointers in Java, C++, and Python. The low, mid, and high pointers divide the array into three sections, and the elements are rearranged to meet the specified sorting criteria.