Pattern 01: Two Pointers (Opposite Ends)

0. The Template (Copy-Paste Skeleton)

Memorise one skeleton. Every opposite-ends problem is this loop with the if/else body swapped.

// TEMPLATE A — OPPOSITE ENDS (converging pointers) on a SORTED array
int twoPointers(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left < right) {                 // '<' not '<=' — l==r is a single element
        int sum = arr[left] + arr[right];  // KNOB: whatever "current value" means

        if (sum == target)     return ...; // found
        else if (sum < target) left++;     // need BIGGER  → move left rightwards
        else                   right--;    // need SMALLER → move right leftwards
    }
    return -1;
}

// TEMPLATE B — SAME DIRECTION (fast/slow write pointer) — in-place filtering
int removeInPlace(int[] arr) {
    int slow = 0;                          // next position to WRITE
    for (int fast = 0; fast < arr.length; fast++) {   // scans/READS everything
        if (keep(arr[fast])) {
            arr[slow++] = arr[fast];       // compact survivors to the front
        }
    }
    return slow;                           // new logical length
}

// TEMPLATE C — EXPAND FROM CENTER (palindromes)
for (int center = 0; center < s.length(); center++) {
    expand(s, center, center);             // odd-length palindrome
    expand(s, center, center + 1);         // even-length palindrome
}
void expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    // s.substring(l + 1, r) is the palindrome; length = r - l - 1
}

Which template?

The problem says	Use
sorted array, find a pair/triplet summing to X	A
container/water/area between two lines	A
remove / move / dedupe in place, keep order	B
partition (Dutch flag, move zeroes)	B
longest palindromic substring	C

The 3 rules that prevent every bug

1. while (left < right) — using <= makes left == right compare an element with itself.
2. Move exactly one pointer per iteration, unless you’re deliberately skipping duplicates.
3. Skipping duplicates (3Sum): while (l < r && arr[l] == arr[l+1]) l++; after recording a hit.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Find a pair that satisfies a condition” (sum, difference, product)
• Input array is sorted (or can be sorted)
• “Find two elements” with a constraint
• “Reverse” or “Palindrome” keywords
• “Container / Area” problems involving width and height

The Algorithm (Pseudocode)

left = 0
right = array.length - 1

while (left < right):
    compute result using array[left] and array[right]

    if result == target:
        return answer
    else if result < target:
        left++          // need a bigger value
    else:
        right--         // need a smaller value

The ‘Trick’ to Know

• Two pointers only work correctly on sorted data for sum/pair problems. If the array isn’t sorted, you must sort it first (O(n log n)) or use a HashMap instead.
• For 3Sum, fix one element and run two pointers on the rest - reducing O(n^3) to O(n^2).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Two Sum II (Sorted Array) - LC 167

Brute Force: O(n^2)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return new int[]{};
    }
}

Optimal: Two Pointers - O(n)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];

            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{};
    }
}

Java Architecture Insights

• Why not ArrayList? We use primitive int[] because there’s no need for dynamic sizing. Avoids autoboxing overhead.
• Why while (left < right) not <=? Two distinct elements needed - they can never be the same index.

---

3. Mental Model & Visualization

ASCII Diagram (Two Sum II, target = 9)

Array: [2, 3, 5, 7, 11]
        L              R    sum = 2+11 = 13 > 9 → R--
        L           R       sum = 2+7  = 9  → FOUND!

Result: indices [1, 4]

Senior Mental Trigger

“Sorted input + pair search = squeeze from both ends.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 125	Valid Palindrome	Easy
LC 167	Two Sum II (Input Array Is Sorted)	Medium
LC 283	Move Zeroes	Easy
LC 344	Reverse String	Easy
LC 977	Squares of a Sorted Array	Easy

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 11	Container With Most Water	Medium
LC 15	3Sum	Medium
LC 42	Trapping Rain Water	Hard
LC 75	Sort Colors (Dutch National Flag)	Medium
LC 16	3Sum Closest	Medium

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Brute Force	O(n^2)	O(1)	Nested loop checking all pairs
Two Pointers	O(n)	O(1)	Single pass with two indices
HashMap	O(n)	O(n)	Alternative when array unsorted