Two Pointers (双指针）

Abstract

---

• Mainly used to solve Array, OOP & Linked List related problems
• Reduce time complexity by one dimension, O(n^2) to O(n)

Fast-Slow Pointers

---

• Two Pointers (双指针） move at a different speed in the same direction
• Convert 1 nested for loop into 1 single for loop
• Can be used to remove elements from array in-place
• Can be used to determine if Linked List is a Circular Linked List

Leetcode Questions

• 27. Remove Element
• 19. Remove Nth Node From End of List
• 142. Linked List Cycle II

Left-Right Pointers

---

• Two Pointers (双指针） move in an opposite direction at the same or different speed
• Can be used to reverse a sorted array In-Place like Reverse String and implementing Binary Search

// Java
 
public void twoPointerSort(int left, int right, int[] arr) {
    int temp;
    while (left < right) {
        temp = arr[right];
        arr[right--] = arr[left];
        arr[left++] = temp;
    }
}

Leetcode Questions

• 977. Squares of a Sorted Array
• 15. 3Sum
• 18. 4Sum
• 344. Reverse String
• 541. Reverse String II

Sliding Window

---

• Two Pointers (双指针） move in the same direction at the same or different speed
• Can be used to find Minimum Size Subarray that the sum of the elements is equal or greater than the given target value, can also be used to find longest substring without repeating characters

3 questions to ask

1. What should be inside the Two Pointers Window?
2. When should we increment the left pointer?
3. When should we increment the right pointer?

Need to keep track of the element frequency?

We can use Hash Map to keep track the element frequency.

Terminologies

---

Two Pointers Window

• The elements within the left and right pointers when we are performing Sliding Window
• The operation of expanding and shrinking the window is usually the same