Two Pointers

Two pointers is not a trick for moving two variables. It is a disciplined way to turn a candidate search into a single pass when the input order gives you evidence about what can be safely ignored.

The Core Idea

A brute-force pair search compares every item with every other item. Two pointers asks a sharper question: can one comparison tell us which side cannot contain the answer anymore? If yes, one pointer moves and a whole group of candidates disappears.

Scenario: Matching Risk Thresholds

A fraud system has sorted risk scores and needs to find whether two signals combine to a target threshold. A nested loop checks every pair. With millions of signals this is expensive. Because the scores are sorted, the sum of the smallest and largest score tells us which pointer to move.

Same Pattern in Java, Python, and JavaScript

class PairSum {
    static boolean hasPair(int[] values, int target) {
        int left = 0;
        int right = values.length - 1;
        while (left < right) {
            int sum = values[left] + values[right];
            if (sum == target) return true;
            if (sum < target) left++;
            else right--;
        }
        return false;
    }
}

The complexity is O(n) time and O(1) extra memory. The sorted input is not decoration; it is the condition that makes movement safe.

Where Two Pointers Shows Up

• Pair search in sorted arrays.
• Deduplicating sorted records.
• Validating palindromes after normalization.
• Merging sorted streams or pages.
• Compacting arrays in place when removing invalid items.

Field judgmentEngineering Notes

• State what each pointer represents.
• State the invariant before explaining code.
• Every pointer move must discard candidates safely.
• Two pointers often replaces O(n^2) pair checks with O(n).
• If input is unsorted, include sorting cost or choose another approach.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Given a sorted integer array, return whether any two values sum to a target.
• Return whether a string is a palindrome after ignoring non-alphanumeric characters and case.
• Given a sorted array, compact unique values in place and return the new length.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class SortedTwoSum {
    static boolean hasPair(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) return true;

            // Sorted order tells us which side is impossible.
            if (sum < target) left++;
            else right--;
        }
        return false;
    }
}

class ValidPalindrome {
    static boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(text.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(text.charAt(right))) right--;

            char a = Character.toLowerCase(text.charAt(left));
            char b = Character.toLowerCase(text.charAt(right));
            if (a != b) return false;

            left++;
            right--;
        }
        return true;
    }
}

class RemoveDuplicates {
    static int compact(int[] nums) {
        if (nums.length == 0) return 0;

        int write = 1;
        for (int read = 1; read < nums.length; read++) {
            // Sorted input means a new value differs from the previous value.
            if (nums[read] != nums[read - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
}

Solved modelWorked Interview Answer

Given a sorted array, return whether two numbers sum to a target. Because the array is sorted, a sum that is too small proves the left value is too small; a sum that is too large proves the right value is too large.

class TwoSumSorted {
    static boolean hasPair(int[] values, int target) {
        int left = 0, right = values.length - 1;
        while (left < right) {
            int sum = values[left] + values[right];
            if (sum == target) return true;
            if (sum < target) left++;
            else right--;
        }
        return false;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Moving a pointer without proving the move is safe.
• Using two pointers on unsorted data without accounting for sorting cost.
• Forgetting edge cases such as empty arrays, one item, duplicates, or negative values.

Execution guardrailQuick-Start Checklist

• Identify what each pointer means.
• Confirm ordering or monotonic movement exists.
• Define the invariant.
• Prove each move cannot skip the answer.
• State time and space complexity.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice sorted two-sum, valid palindrome, and remove duplicates.
• Compare two pointers with hash-map lookup for pair problems.
• Review sorting cost before applying two pointers to unsorted input.