Important points

  1. Physical significance of the pointer
    → range
    → pair (i, j)
  2. How to initialize the pointer
  3. How to change the pointer / move the pointer
  4. When to stop

Types of Two Pointers

  • Collision — One array, move from two sides to middle.
  • Forward — One array, both move forward.
  • Parallel — Two arrays, each array has been assigned with a pointer

Sample Problem

Given a sorted (in ascending order) integer array nums of n elements and a target value, find if there exists any pair of elements (nums[i], nums[j], i!=j) such that their sum is equal to target.

// Two pointers, O(n)
public boolean isPairSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int start = 0;
int end = nums.length - 1;

while (start < end) {
int sum = nums[start] + nums[end];
if (sum == target) {
return true; // pair exists
} else if (sum < target) {
start++; // move start forward to get larger value
} else {
end--; // move end backward to get smaller value
}
}

// not found
return false;
}

Problems

3.1 Collision

Sub type: Two Sum

3.2 Forward

Sub type: Window

3.3 Parallel

Two arrays, one pointer each.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store