Two-Pointers: Linear Precision

The Two-Pointer technique is one of the most effective ways to optimize O(n²) spatial or temporal complexity down to a lean O(n).

The Strategy

Instead of using nested loops to compare elements (which results in quadratic time), we use two independent pointers—left and right—that move through the data structure based on specific conditions.

Pattern 1: Same Direction (Sliding Window)

Both pointers move from start to end. This is common for finding sub-arrays that meet a specific sum or length criteria.

Pattern 2: Opposite Direction

One pointer starts at index 0 and the other at n-1. They move towards each other until they meet. This is the classic approach for finding pairs in a sorted array (Two Sum II).

Example: Two Sum (Sorted)

Given a sorted array nums and a target, find indices of two numbers such that they add up to the target.

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder result = new StringBuilder();
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0';
                j--;
            }
            // current bit
            result.append(sum % 2);
            // carry for next position
            carry = sum / 2;
        }
        return result.reverse().toString();
    }
}

---

"Two pointers are faster than one nested loop."