Two Pointers is a pattern in which two pointers iterate until one or both of them satisfy the necessary condition. The two-pointer approach is a technique used to solve problems in linear time by using two pointers that traverse through an array. It is often used in arrays to minimise time complexity.
What is a pointer?
A pointer is a reference to an object. That object stores a memory address of another value located in computer memory.
How to use the two-pointer technique?
Two pointer technique is nothing more than a clever optimisation of specific brute-force techniques. It reduces the time complexity by using some type of order rather than necessarily sorting the data.
The pointers in this technique represent either an index or an iteration attribute, such as the node’s next.
Two-pointer technique in Arrays:
Usually when the given array is sorted, we can think of this approach for an optimised solution. Here is an example of a two-pointer approach in Java:
Problem: Given a sorted array of n integers nums and a target value target, find the indices of two numbers such that they add up to target.
Now lets solve this using two pointer approach method:
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0,1]
Explanation: The numbers at index 0 and 1 (2 + 7 = 9) satisfy the condition.
Approach:
1. Create an array result to store the indices of the two numbers.
2. Create two pointers left and right initialised to 0 and nums.length — 1 respectively.
3. In each iteration, calculate the sum of the values at nums[left] and nums[right].
4. If the sum is equal to target, store the indices in result and return it.
5. If the sum is less than target, move the left pointer to the right.
6. If the sum is greater than target, move the right pointer to the left.
7. Repeat steps 3–6 until left is equal to or greater than right.
The time complexity of this approach is O(n) because in the worst case scenario, both pointers will traverse the entire array once.
Let us look at one more example before we look at the code:
class twopoint {
public int[] twoSum(int[] nums, int target) {
//Create an array result to store the indices of the two numbers.
int[] result = new int[2];
//Create two pointers left and right initialized to 0 and nums.length - 1 respectively.
int left = 0, right = nums.length - 1;
//In each iteration, calculate the sum of the values at nums[left] and nums[right].
while (left < right) {
int sum = nums[left] + nums[right];
//If the sum is equal to target, store the indices in result and return it.
if (sum == target) {
result[0] = left;
result[1] = right;
return result;
}
//If the sum is less than target, move the left pointer to the right.
else if (sum < target)
{
left++;
}
//If the sum is greater than target, move the right pointer to the left.
else
{
right--;
}
}
return result;
}
public static void main(String[] args) {
//We are given a sorted array:
int[] nums = {1,2,5,9,10,90};
int target = 14;
twopoint solution = new twopoint();
int[] result = solution.twoSum(nums, target);
System.out.println("Numbers are "+nums[result[0]]+" "+nums[result[1]]);
System.out.println("Indices: " + result[0] + " " + result[1]);
}
}Two pointer technique in Strings:
Here is an example of the two-pointer approach in Java for a string-related problem:
Problem: Given a string, determine if it is a palindrome. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward.
Example:
Input: “wow”
Output: true
Explanation: The string “wow” is a palindrome.
APPROACH
1. Create two pointers left and right initialised to 0 and s.length() — 1 respectively.
2. In each iteration, move the left pointer to the right until it reaches a letter or digit.
3. Similarly, move the right pointer to the left until it reaches a letter or digit.
4. Compare the characters at the indices left and right ignoring the case of the characters.
5. If the characters are not equal, return false.
6. If the characters are equal, move both pointers to the right and left respectively.
7. Repeat steps 2–6 until left is equal to or greater than right.
The time complexity of this approach is O(n) because in the worst case scenario, both pointers will traverse the entire string once.
class twopoint_string {
public boolean isPalindrome(String s) {
//Create two pointers left and right initialized to 0 and s.length() - 1 respectively
int left = 0, right = s.length() - 1;
//In each iteration, move the left pointer to the right until it reaches a letter or digit
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
//move the right pointer to the left until it reaches a letter or digit
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
//Compare the characters at the indices left and right ignoring the case of the characters
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
//If the characters are not equal, return false.
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
String s = "wow";
twopoint_string solution = new twopoint_string();
boolean result = solution.isPalindrome(s);
System.out.println("Palindrome: " + result);
}
}Variants of Two Point Approach:
1. Two-Pointer Traversal: In this variant, two pointers traverse the array from the opposite ends, either from the start and end of the array or from the end and start of the array. This is useful for solving problems like finding two elements that sum to a target value, finding the middle of a linked list, and checking if a string is a palindrome.
2. Slow and Fast Pointers: In this variant, a slow pointer moves one step at a time while a fast pointer moves two steps at a time. This is useful for finding the middle of a linked list and for detecting cycles in a linked list.
3. Left and Right Pointers: In this variant, two pointers, one starting from the left and the other starting from the right, move towards each other. This is useful for solving problems like finding the largest rectangle in a histogram, finding the largest sub-array with equal number of zeros and ones, and merging two sorted arrays.
An example of fast & slow pointer:
For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.
