Two-pointer techniques

Start one pointer at each end of a sorted array and move them inward. Each comparison decides which end to drop, so the loop runs at most n - 1 times instead of the n(n - 1)/2 pair checks of a nested loop.

Other problems with this shape: checking a palindrome, reversing an array in place, and container with most water, where you always move the shorter wall because the taller one cannot help a narrower container.

1static boolean isPalindrome(String s) {
2    int lo = 0, hi = s.length() - 1;
3    while (lo < hi) {
4        if (s.charAt(lo) != s.charAt(hi)) return false;
5        lo++;
6        hi--;
7    }
8    return true;
9}

Both pointers move left to right. The read pointer scans every element; the write pointer marks where the next kept element goes. Everything before write is the finished result.

This compacts an array in place in one pass and O(1) extra space. Removing duplicates from a sorted array is the standard example.

1public static int removeDuplicates(int[] arr) {      // arr is sorted
2    if (arr.length == 0) return 0;
3    int write = 1;                                  // arr[0..write-1] is the unique prefix
4    for (int read = 1; read < arr.length; read++) {
5        if (arr[read] != arr[write - 1]) {
6            arr[write] = arr[read];
7            write++;
8        }
9    }
10    return write;
11}

Move one pointer one step at a time and another two steps. If the structure has a cycle, the fast pointer laps the slow one and they meet; if not, the fast pointer reaches the end. This is Floyd's tortoise and hare algorithm.

After they meet, reset one pointer to the start and move both one step at a time: they meet again exactly at the entrance of the cycle. The animation treats each array cell as a node pointing to index next[i], which is how “find the duplicate number” is solved in O(1) space.

1static ListNode middle(ListNode head) {         // same idea: fast reaches the end when slow is halfway
2    ListNode slow = head, fast = head;
3    while (fast != null && fast.next != null) {
4        slow = slow.next;
5        fast = fast.next.next;
6    }
7    return slow;
8}

1static int cycleStart(int[] next) {          // node i points to node next[i]; start at 0
2    int slow = 0, fast = 0;
3    do {
4        slow = next[slow];                     // one step
5        fast = next[next[fast]];               // two steps
6    } while (slow != fast);                    // they meet somewhere on the cycle
7    slow = 0;
8    while (slow != fast) {                     // equal speed now
9        slow = next[slow];
10        fast = next[fast];
11    }
12    return slow;                               // first node of the cycle
13}

Partitioning moves the elements that satisfy a condition to the front. With a read pointer and a write pointer and a swap, the kept elements also keep their relative order, which is what “move zeroes” requires.

Quick sort's Lomuto partition is the same pattern with the condition arr[j] < pivot. With three regions (less, equal, greater) it becomes the Dutch national flag partition from lesson 18.02.

1public static void moveZeroes(int[] arr) {
2    int write = 0;                        // arr[0..write-1]: non-zeros, original order
3    for (int read = 0; read < arr.length; read++) {
4        if (arr[read] != 0) {
5            swap(arr, write, read);
6            write++;
7        }
8    }
9}

Given a sorted array and a target, find two indices whose values add up to the target. If the current sum is too small, the left value cannot pair with anything (even the largest remaining value is not enough), so move left right. If it is too large, move right left.

Each step permanently rules out one value, so the search is O(n). On unsorted data, either sort first (O(n log n)) or use a hash map of seen values (O(n) expected).

1public static int[] twoSum(int[] arr, int target) {     // arr is sorted
2    int lo = 0, hi = arr.length - 1;
3    while (lo < hi) {
4        int sum = arr[lo] + arr[hi];
5        if (sum == target) return new int[] { lo, hi };
6        if (sum < target) lo++;          // need a bigger sum
7        else hi--;                       // need a smaller sum
8    }
9    return new int[] { -1, -1 };
10}

In a sorted array, equal values are adjacent, so a value is new exactly when it differs from the last kept value. Allowing each value up to twice only changes the comparison to arr[read] != arr[write - 2].

On unsorted data, deduplicate with a LinkedHashSet to keep first-seen order, or sort first if order does not matter.

1static int removeDuplicatesAtMostTwice(int[] arr) {   // sorted input
2    int write = 0;
3    for (int x : arr) {
4        if (write < 2 || x != arr[write - 2]) arr[write++] = x;
5    }
6    return write;
7}