Tammy Vo

Posted on

# Two Pointer Technique

When to use: Optimal way to solve problems related to arrays, strings and linked list in O(N) time.

Arrays/Strings: Two pointers, each starting from the beginning and the end until they both meet.
Example Problem: Two Sum II - Input Array Is Sorted

``````class Solution {
public int[] twoSum(int[] numbers, int target) {
// use two pointer technique because the input is sorted.
int start = 0;
int end = numbers.length - 1;
int [] result = new int [2];

while (start < end){
int sum = numbers[start] + numbers[end];

if (sum == target){
result[0] = start + 1;
result[1] = end + 1;
break;
}

if (sum < target){
start++;
} else {
end--;
}
}
return result;
}
}
``````

Linked List: One pointer moving at a slow pace, while the other pointer moves at twice the speed.
Example Problem: Linked List Cycle

``````public class Solution {
public boolean hasCycle(ListNode head) {

return false;
}

ListNode slow = head;
ListNode fast = head;

while(fast != null && fast.next != null){

slow = slow.next;
fast = fast.next.next;

if(slow == fast){
return true;
}
}
return false;
}
}
``````