Two Pointer Technique: Solving Pair and Partition Problems in O(n)

Scenario context

Place one pointer at the start and one at the end of a sorted array. Move them toward each other based on a comparison condition. Every classic pair/partition problem that naively runs in O(n²) collapses to O(n) with this one idea — and mastering it unlocks Three Sum, Container With Most Water, and dozens of interview problems in one mental model.

You have a sorted array and need to find two numbers that sum t…

This walkthrough focuses on The O(n²) Trap: Why Brute-Force Pair Searches Break at Scale.

Before making a design choice, clarify:

• You have a sorted array and need to find two numbers that sum to a target.
• The first instinct is a nested loop: for every element, scan the rest of the array for a match.
• That works, but it runs in O(n²) time.

Concepts in play: jvm-internals-and-garbage-collection, core-algorithm-patterns, database-indexing, api-gateway

Stage 1 — Sorted Arrays and the Convergence Property

• The technique only works because sorting gives you a total order you can exploit.
• When left and right are two indices in a sorted array, the following invariants hold at all times: - arr[left] is the smallest unconsidered value on the left.
• • arr[right] is the largest unconsidered value on the right.
• • If arr[left] + arr[right] target , then no element to the right of left can pair with arr[right] to produce a smaller sum — so you must move right left.

Observable outcome: - If arr[left] + arr[right] target , then no element to the right of left can pair with arr[right] to produce a smaller sum — so you must move right left.

Stage 2 — How Two Pointers Converge: The Decision Loop

• The canonical template is compact.
• Set left = 0 and right = n - 1 .
• In each loop iteration, compute the condition using both values and move the appropriate pointer.
• The loop invariant is left < right .

// Generic two-pointer template
int left = 0, right = arr.length - 1;

while (left < right) {
    int value = compute(arr[left], arr[right]);  // e.g. sum, area, comparison

    if (value == target) {
        // Found solution — record it, then decide whether to keep searching
        left++;
        right--;
    } else if (value < target) {
        left++;   // Need a larger value — move left inward
    } else {
        right--;  // Need a smaller value — move right inward
    }
}

Observable outcome: The loop invariant is left < right .

Stage 3 — Visualizing Two Pointers Converging on a Sorted Array

• Each branch eliminates at least one candidate, guaranteeing the loop terminates in at most n steps.
• For Three Sum, picture a fixed outer pointer scanning left to right.
• For each fixed value, the two pointers independently converge on the remaining subarray to find pairs that complement it.

flowchart TD
    A([Start: left=0, right=n-1]) --> B{left < right?}
    B -- No --> Z([Done])
    B -- Yes --> C[Compute sum = arr left + arr right]
    C --> D{sum vs target}
    D -- equal --> E[Record pair left++ and right--]
    D -- too small --> F[left++ Need larger value]
    D -- too large --> G[right-- Need smaller value]
    E --> B
    F --> B
    G --> B

flowchart LR
    A([Fix arr i]) --> B([left = i+1 right = n-1])
    B --> C{left < right}
    C -- Yes --> D{triplet sum vs 0}
    D -- zero --> E[Record triplet Skip duplicates left++ right--]
    D -- negative --> F[left++]
    D -- positive --> G[right--]
    E --> C
    F --> C
    G --> C
    C -- No --> H([Next i])

Observable outcome: For each fixed value, the two pointers independently converge on the remaining subarray to find pairs that complement it.

Stage 4 — Where Two Pointers Show Up: Arrays, Strings, and Intervals

• The two-pointer pattern appears in production code and systems far beyond competitive programming: In-place array partitioning: Languages like Java use dual-pivot quicksort (introduced in Java 7) where two pivots and th…
• String palindrome validation: Every palindrome checker — from input validation libraries to DNA sequence analyzers — uses the same convergence loop on the character array.
• Check s[left] == s[right] , move inward.
• Merge step in merge sort: The merge of two sorted halves walks two pointers forward through each half, picking the smaller element at each step.

Observable outcome: Merge step in merge sort: The merge of two sorted halves walks two pointers forward through each half, picking the smaller element at each step.

Stage 5 — When Sorting Costs More Than It Saves

• Two pointers are not universally applicable.
• The main failure modes: Unsorted data with expensive sort: If you can't sort the input (it's a stream, or the sort cost is prohibitive), two pointers don't apply directly.
• A hash-set approach at O(n) time, O(n) space is better for a single query.
• However, if you need to answer many queries against the same array, paying O(n log n) once to sort and then running O(n) per query is usually worth it.

Observable outcome: However, if you need to answer many queries against the same array, paying O(n log n) once to sort and then running O(n) per query is usually worth it.

Stage 6 — Choosing Between Two Pointers and Hash-Set Lookup

• The decisive question: Is the data sorted, or can it be sorted at acceptable cost?
• If yes, two pointers wins on space.
• If the data can't be sorted and space isn't a constraint, reach for a hash set.

Observable outcome: If the data can't be sorted and space isn't a constraint, reach for a hash set.

End-to-end outcome

After working through the stages, you should be able to explain:

• The off-by-one on loop termination.
• The condition is left < right , not left <= right .
• • The core idea is to place pointers at both ends of a sorted array and move them inward based on a comparison condition.
• Each move eliminates a column of candidates.

Alternatives considered

The source focuses on one primary design. A second architecture is not compared, so no alternative is invented here.

Failure and degraded modes

The source does not isolate a separate failure mode. Limits that matter for the scenario are called out in the stage decisions above.