Algorithm Patterns: Two Pointers

The two-pointer pattern is used when we are dealing with sorted arrays or linked lists and needs to find a set of elements (subset, two elements, or three elements) that satisfy certain constraints.

Example One: Pair With Target Sum

Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

Input: [1, 2, 3, 5, 6, 9], target=8
Output: [1, 4]
Explanation: The numbers at index 1 and 4 add up to 8: 2+6=8

First Approach: Two Pointer Approach

We’ll start with two pointers, start, and end, one at the beginning and one at the end of the array. Then we’ll add the two elements to see if they’re bigger or smaller than the target. If the result is greater than the target, we subtract one from the end pointer; otherwise, we add one to the start pointer. We’ll keep going until we find the two elements we’re looking for. It should be noted that this method will only work if the array is sorted.

Java Code

public static int[] search(int[] arr, int target) {
    int start = 0, end = arr.length - 1;
    while (start < end) {
      int currentSum = arr[start] + arr[end];
      if (currentSum == target)
        return new int[] { start, end }; // found the pair

      if (target > currentSum)
        start++; // we need a pair with a bigger sum
      else
        end--; // we need a pair with a smaller sum
    }
    return new int[] { -1, -1 };
}

Time Complexity

The time complexity of the above algorithm is O(N), where ’N’ is the total number of elements in the given array.

Space Complexity

The Space complexity of this algorithm is O(1). Because we didn’t use any extra memory.

Second Approach: HashMap Approach

Instead of using two pointer approach, we can use Utilize hashmap. we will start iterating through the array one number at a time. Assume we are at number ‘X’ during our iteration and need to find ‘Y’ so that “X + Y == Target-Y”. Here, we will do two things:

1. Search for ‘Y’ (which is equivalent to “Target-X”) in the HashTable. If it is there, we have found the required pair.
2. Otherwise, insert “X” in the HashTable, so that we can search it for the later numbers.

public static int[] search(int[] arr, int target) {
    HashMap<Integer, Integer> map = new HashMap<>(); // to store numbers and indices
    for (int i = 0; i < arr.length; i++) {
      if (map.containsKey(target - arr[i]))
        return new int[] { map.get(target - arr[i]), i };
      else
        map.put(arr[i], i); // put the number and its index in the map
    }
    return new int[] { -1, -1 }; // pair not found
}

Time Complexity

The time complexity of the above algorithm is O(N), where ’N’ is the total number of elements in the given array.

Space Complexity

The Space complexity of this algorithm is O(N). because we pushed ’N’ numbers in the HashTable.

Example Two: Remove Duplicates

Given an array of sorted numbers, remove all duplicate number instances from it in-place, such that each element appears only once.

Input: [2, 3, 3, 3, 6, 9]
Output: 4
Explanation: The first four elements after removing the duplicates will be [2, 3, 6, 9].

In this problem, we’ll use two pointers: one to iterate the array and another to place the next non-duplicate number. So we’ll iterate through the array, and whenever we see a non-duplicate number, we’ll move it next to the last non-duplicate number we saw.

Java Code

public static int remove(int[] arr) {
    int nextNonDuplicate = 1; // index of the next non-duplicate element
    for (int i = 0; i < arr.length; i++) {
      if (arr[nextNonDuplicate - 1] != arr[i]) {
        arr[nextNonDuplicate] = arr[i];
        nextNonDuplicate++;
      }
    }

    return nextNonDuplicate;
}

Time Complexity

The time complexity of the above algorithm is O(N), where ’N’ is the total number of elements in the given array.

Space Complexity

The Space complexity of this algorithm is O(1). Because we didn’t use any extra memory.

Two Pointers — LeetCode Problems

Here you can find many questions to solve on LeetCode

The more you practice the better you get