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

// 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
• 3 points to consider
  1. What should be inside the Window?
  2. When should we increment the left pointer?
  3. When should we increment the right pointer?

Leetcode Questions

• 209. Minimum Size Subarray Sum

Terminologies

---

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