Two Pointers (双指针)

Abstract

---

• Mainly used to solve Array and 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
• Can be used to remove elements from array in-place
• Can be used to determine if Linked List is a Circular Linked List
• Convert 1 nested for loop into 1 single for loop

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

// Reverse a sorted array in-place
 
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
• 125. Valid Palindrome

Two-Pointers Sliding Window

---

• Use Two Pointers (双指针): left pointer and right pointer to represent a window
• Move right pointer to find a valid window, or an invalid window, depends on what the problem wants
• When a valid window is found, move left pointer to find a smaller window or new valid window, or desired answer in the valid window
• When the window isn’t valid anymore, move the left pointer

Tip

The operation of expanding and shrinking the window is usually the same.

3 questions to ask

1. What should be inside the two-pointers sliding window?
2. When should we increment the left pointer?
3. When should we increment the right pointer?

Keep track of the window

We can use Hash Map to keep track the element frequencies in the window.

This is needed when solving Longest Repeating Character Replacement problem, where we need the highest element frequency in a sliding window to ensure the two-pointers sliding window is valid while expanding the window. Shrinking the window when it isn’t valid anymore.

This is needed when solving Find All Anagrams in a String problem, where we need to keep track whether the elements inside the window contain all the characters of the given anagram. If so, we can start shrinking the window to find the anagram.

This is needed when solving Minimum Window Substring problem, where we need to keep track whether the elements inside the window contain all the characters of the given string. If so, we can start shrinking the window to find the smallest substring that contains all the characters.

More examples

The sliding window technique can be used to find Minimum Size Subarray with sum that equals or exceeds the target value, as well as the find longest substring without repeating characters