Two Pointers
Iterating two pointers across an array
Two pointers is a technique commonly used to search for pairs in a sorted array. The idea is to create two markers (pointers) to keep track of your position in the array. The pointers are then iterated across an array to search for a pair of indices that satisfy some condition in linear time.
In this article, we will go over the textbook example of a two-pointers problem: finding two array elements that sum up to a certain number.
Naively, the problem can be solved by using two for loops, checking each pair of elements. However, this solution runs in O(n2) time, which may exceed the time limit for test cases with larger inputs. A more efficient method to solve this problem would be to use two-pointers.
With two pointers, the first pointer starts at the beginning of the array, and the second pointer starts at the end of the array. Using a while loop, the sum of the first and second pointers is compared to the desired sum. If the sum is larger than desired, the second pointer is moved down one element; notice that because the array is sorted from least to greatest, moving the right pointer to the left by one element decreases the overall sum. If the sum is smaller than desired, using similar logic as before, the first pointer is moved up one element.
Note that this method can only be used on a sorted array. Therefore, the time complexity of this solution would be O(n log n) if the array has not yet been sorted, and O(n) if it has been sorted; both are more efficient than the naive O(n2) solution.
An implementation of the said algorithm can be found below.
the implementation below uses a single while loop, but there are other implementations that include for loops or a combination of for loops and while loops.
Code:
arr = [1, 3, 6, 8, 10]
def two_pointers(arr, sum):
  first = 0
  second = len(arr)-1
  while first<second:
    if arr[first]+arr[second]>sum:
      second=second-1
    elif arr[first]+arr[second]<sum:
      first=first+1
    else:
      print(first, second)
      return

two_pointers(arr, 14)
Output:
2, 3
Code:
public class Main {
  static int[] arr = {1, 3, 6, 8, 10};

  public static void two_pointers (int[] arr, int sum) {
    int first = 0;
    int second = arr.length-1;
    while (first<second) {
      if (arr[first]+arr[second]>sum) {
        second--;
      }
      else if (arr[first]+arr[second]<sum) {
        first++;
      }
      else {
        System.out.println(first + " " + second);
        return;
      }
      }
  }

   public static void main(String[] args) {
      two_pointers(arr, 14);
  }
}
Output:
2, 3
Code:
#include <bits/stdc++.h>
using namespace std;

vector<int> arr = {1, 3, 6, 8, 10};

void two_pointers (vector<int> arr, int sum) { 
  int first = 0;
  int second = arr.size()-1;
  while (first<second) {
    if (arr[first]+arr[second]>sum) {
      second--;
    }
    else if (arr[first]+arr[second]<sum) {
      first++;
    }
    else {
      cout << first << " " << second << endl;
      return;
    }
  }
}

int main() {
  two_pointers(arr, 14);
}
Output:
2, 3
You can play around with all the code we've used in this article on Replit:
Join our discord server for updates, announcements, future event planning, to ask questions, or just for fun!
Copyright ©2021 Howard County Hour of Code