Identifying Two Pointer Reduction

When Direct Application Isn’t Enough

The direct two-pointer technique works perfectly when the problem already fits the template — traverse from both ends, do some work, converge. But some problems don’t fit that template in their original form. They need to be transformed first.

The key idea: if the problem can be reduced to an equivalent problem that does fit the two-pointer template, and the solution to the reduced problem is guaranteed to be the solution to the original — then we’re good.

This transformation is called a reduction.

The Diagnostic Questions

Before attempting a reduction, run through these four questions:

If sorting unlocks Q3 (traversal from both ends becomes meaningful), you almost certainly have a two-pointer reduction problem.

The Example: Two Sum

Problem: Given an array arr of integers and a target, find two elements whose sum equals the target.

Let’s use arr = [3, 5, 2, 8, 7, 1, 9, 4], target = 13.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
block-beta
  columns 8
  A["3"] B["5"] C["2"] D["8"] E["7"] F["1"] G["9"] H["4"]
  PAIR1["↑ 5 + 8 = 13 ✓"]:4 PAIR2["↑ 4 + 9 = 13 ✓"]:4

Find two numbers with the given sum (13) in the array — pairs (5,8) and (4,9) both qualify.

Brute Force: O(n²)

The naive solution checks every pair with nested loops:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Start["for i in range(n)"]
  Inner["for j in range(i+1, n)"]
  Check{"arr[i] + arr[j]\n== target?"}
  Return(["return [arr[i], arr[j]]"])
  Continue["continue"]
  NotFound(["return []"])

  Start --> Inner --> Check
  Check -->|"yes"| Return
  Check -->|"no"| Continue --> Inner
  Inner -->|"j exhausted"| Start
  Start -->|"i exhausted"| NotFound

Brute-force nested loops check every pair — O(n²) time, correct but slow. For n=8 that's 28 pairs checked.

from typing import List

def two_sum_brute(arr: List[int], target: int) -> List[int]:
    # Fix one element of the pair at position i and search for its complement
    for i in range(len(arr)):
        # Start j at i+1 to avoid using the same element twice and re-checking pairs
        # (pair (i,j) and (j,i) are the same — j>i ensures we only check each pair once)
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:  # Found a valid pair
                return [arr[i], arr[j]]
    return []  # Exhausted all pairs — no solution exists

print(two_sum_brute([3, 5, 2, 8, 7, 1, 9, 4], 13))  # [5, 8]

arr = [3, 5, 2, 8, 7, 1, 9, 4],  target = 13

i=0 (3):
  j=1 (5): 3+5= 8 ≠ 13
  j=2 (2): 3+2= 5 ≠ 13
  j=3 (8): 3+8=11 ≠ 13
  j=4 (7): 3+7=10 ≠ 13
  j=5 (1): 3+1= 4 ≠ 13
  j=6 (9): 3+9=12 ≠ 13
  j=7 (4): 3+4= 7 ≠ 13

i=1 (5):
  j=2 (2): 5+2= 7 ≠ 13
  j=3 (8): 5+8=13 == 13 → return [5, 8] ✓

Total pairs checked: 10 out of 28 possible (got lucky — answer found early)
Worst case: all 28 pairs checked → O(n²)

Applying the Diagnostic Questions

Q1 — Why “order doesn’t matter here”?

WHAT: The problem asks for the values of the two elements that sum to target — it doesn’t care which indices they lived at originally.

WHY it matters: Order being irrelevant is the permission slip to sort. Sorting rearranges elements, which normally destroys positional information — but since we don’t need positions here, we lose nothing.

Concrete check: arr = [3, 5, 2, 8, 7, 1, 9, 4], target = 13. The pair (5, 8) is valid whether the array is unsorted or sorted as [1, 2, 3, 4, 5, 7, 8, 9]. The answer stays the same.

What breaks if order DID matter? If the problem asked for the indices of the pair (like LeetCode Two Sum), sorting would shuffle elements and invalidate any index-based answer. You’d need a hash map instead — sorting is off the table.

Memory trick:

Q1 is your sorting gate.

• If order matters → no sort → no two-pointer reduction.
• If order doesn’t matter → sort is free → reduction is possible.

Q2 — Why “we always need two items simultaneously”?

WHAT: Two-pointer requires exactly two active cursor positions — one tracking the “left candidate” and one tracking the “right candidate” at every step.

WHY it matters for this problem: Summing a pair means we must hold two elements at once. There’s no way to answer “do two numbers sum to target?” by looking at one element at a time — you always need a partner for comparison.

Concrete check: At any given moment, we have arr[left] and arr[right] in hand. We compute arr[left] + arr[right] and decide which pointer to move. If we only tracked one pointer, we’d have no way to evaluate the sum.

What breaks without Q2? If the problem were “find one element equal to target”, a single pointer suffices — no two-pointer needed. Q2 is the check that ensures the two-pointer structure is actually necessary.

Q3 — Why “No” on the unsorted array, and why sorting flips it to “Yes”?

This is the most important question — it’s the one that unlocks (or blocks) the entire reduction.

On the unsorted array — Why “No”:

On [3, 5, 2, 8, 7, 1, 9, 4], arr[0] = 3 and arr[7] = 4 have no special relationship. Left isn’t smallest, right isn’t largest — they’re just two arbitrary elements.

If 3 + 4 = 7 < 13, should you move left or right? You genuinely don’t know. Moving left could give you a smaller number (e.g. arr[2] = 2), making things worse. There’s no decisive direction — every move is a guess.

After sorting — Why “Yes”:

Sort to [1, 2, 3, 4, 5, 7, 8, 9]. Now:

• arr[left] is always the minimum of all remaining elements
• arr[right] is always the maximum of all remaining elements

This gives you decisive power at every step:

Concrete trace (target = 13):

• left=0, right=7: 1 + 9 = 10 < 13 → left++
• left=1, right=7: 2 + 9 = 11 < 13 → left++
• left=2, right=7: 3 + 9 = 12 < 13 → left++
• left=3, right=7: 4 + 9 = 13 == 13 → found (4, 9) ✓

What breaks if you run two pointers on the unsorted array? You’d miss valid pairs. On [3, 5, 2, 8, 7, 1, 9, 4], left=0, right=7 gives 3 + 4 = 7 < 13, so you’d move left to index 1. But arr[1] = 5 and moving left was wrong — the valid pair (5, 8) is at indices 1 and 3, nowhere near the ends. Without sorted order, “move left” has no guaranteed meaning.

Q4 — Why “chained reduction” is the key unlock?

WHAT: Q4 is the “what if?” question — when the direct answers to Q1–Q3 don’t immediately enable two pointers, ask whether a transformation of the problem does.

WHY it works here: The original problem fails Q3 (unsorted, no decisive direction). But sorting is a legal transformation because Q1 tells us order doesn’t matter. After sorting, Q3 becomes Yes. The problem is now solvable with two pointers.

The chain:

Original problem → sort (allowed because Q1=No) → Sorted problem → Q3=Yes → two-pointer applies

HOW to apply Q4 in general: whenever Q3 is No, ask:

• Can I sort? (Is Q1 = No?)
• Can I preprocess in another way (hash map, prefix sum, frequency count) that creates a useful structure?

If yes to either, you may be able to reduce the problem into something two-pointer-friendly. Sort is the most common such transformation.

The critical observation: sorting establishes a special relationship between items when traversed from both ends — the left pointer always sees the minimum of what’s left, the right pointer always sees the maximum. Because of this, every pointer move has a guaranteed effect: moving left right always increases the sum, moving right left always decreases it. No guessing, no backtracking.

Two-Pointer Solution

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph SORTED["Sorted array:  [1, 2, 3, 4, 5, 7, 8, 9],  target = 13"]
    direction LR
    L(["left=0"]) --> N1["1"] --- N2["2"] --- N3["3"] --- N4["4"] --- N5["5"] --- N6["7"] --- N7["8"] --- N8["9"]
    N8 --> R(["right=7"])
  end

Sorted array with two pointers — left = 0 points at the smallest element, right = n−1 points at the largest.

from typing import List

def two_sum(arr: List[int], target: int) -> List[int]:
    # Reduction step: sort the array so left=min, right=max at every step.
    # Sorting is safe here because we only need values, not original indices (Q1=No).
    arr.sort()

    left  = 0           # Points at the current minimum of remaining elements
    right = len(arr) - 1  # Points at the current maximum of remaining elements

    while left < right:  # Stop when pointers meet — no valid unseen pairs remain
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return [arr[left], arr[right]]  # Found the pair

        elif current_sum < target:
            # arr[right] is already the MAX — no larger partner exists for arr[left].
            # The only way to increase the sum is to move left rightward (to a bigger value).
            left += 1

        else:  # current_sum > target
            # arr[left] is already the MIN — no smaller partner exists for arr[right].
            # The only way to decrease the sum is to move right leftward (to a smaller value).
            right -= 1

    return []  # Pointers crossed — no valid pair found

print(two_sum([3, 5, 2, 8, 7, 1, 9, 4], 13))  # [4, 9]

Original:  [3, 5, 2, 8, 7, 1, 9, 4]
After sort: [1, 2, 3, 4, 5, 7, 8, 9]   left = 0,  right = 7

Step 1 │ left=0 (1),  right=7 (9) │  1+ 9=10 < 13 │ 9 is the MAX — 1 can never reach 13 → left++
Step 2 │ left=1 (2),  right=7 (9) │  2+ 9=11 < 13 │ 9 is the MAX — 2 can never reach 13 → left++
Step 3 │ left=2 (3),  right=7 (9) │  3+ 9=12 < 13 │ 9 is the MAX — 3 can never reach 13 → left++
Step 4 │ left=3 (4),  right=7 (9) │  4+ 9=13 == 13 → return [4, 9] ✓

Total steps: 4 vs 10+ in brute force.
Each step discards one element permanently — no re-visiting, no wasted work.

Proof of Correctness

This is the crucial part. Why is it safe to discard elements?

Case 1: arr[left] + arr[right] < target → discard arr[left]

arr[right] is the maximum value available. If even the maximum can’t make arr[left] reach target, no other element can either. Every pair containing arr[left] has already been virtually checked — all have sum < target.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph ARR["[1, 2, 3, 4, 5, 7, 8, 9]  target=13"]
    direction LR
    L0(["left=0"]) --> E1["1"] --- E2["2"] --- E3["3"] --- E4["4"] --- E5["5"] --- E6["7"] --- E7["8"] --- E8["9"]
    E8 --> R0(["right=7"])
  end
  NOTE["1 + 9 = 10 < 13\narr[right]=9 is the MAX\n∴ all pairs with 1 have sum < 13\n→ safely discard 1"]
  E1 -.->|"all pairs < 13"| NOTE

All pairs containing arr[left] have sum < target — discard arr[left] by incrementing left.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph ARR2["After left++:  [✗, 2, 3, 4, 5, 7, 8, 9]"]
    direction LR
    DISC["1 ✗"] --- F2["2"] --- F3["3"] --- F4["4"] --- F5["5"] --- F6["7"] --- F7["8"] --- F8["9"]
    L1(["left=1"]) --> F2
    F8 --> R1(["right=7"])
  end

Discard arr[left] by incrementing left — the discarded element is never considered again.

Case 2: arr[left] + arr[right] > target → discard arr[right]

arr[left] is the minimum of all remaining elements. If even the minimum makes arr[right] exceed target, no other element will do better. Every pair containing arr[right] exceeds target.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph ARR3["Remaining: [2, 3, 4, 5, 7, 8, 9]  target=13"]
    direction LR
    L2(["left=1"]) --> G2["2"] --- G3["3"] --- G4["4"] --- G5["5"] --- G6["7"] --- G7["8"] --- G8["9"]
    G8 --> R2(["right=7"])
  end
  NOTE2["2 + 9 = 11 < 13 → discard 2\n3 + 9 = 12 < 13 → discard 3\n4 + 9 = 13 == target → ✓ found!"]
  G2 -.-> NOTE2

All pairs of previously discarded elements were already considered before discarding — the invariant is maintained throughout all iterations.

The invariant: we only discard arr[right] after confirming that every remaining element (those not yet discarded) pairs with arr[right] to give a sum > target. The previously discarded elements were already paired with arr[right] and considered before being discarded.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  INV["Invariant: every pair is considered\nbefore either element is discarded"]
  D1["When arr[left] is discarded:\narr[left] paired with all elements\nfrom arr[left+1] to arr[right]\n(right is still the max)"]
  D2["When arr[right] is discarded:\narr[right] paired with all elements\nfrom arr[left] to arr[right-1]\n(left is now the min of remainder)"]
  INV --> D1
  INV --> D2

Discard arr[right] by decrementing right — the invariant guarantees no valid pair is missed.

Problems in This Category

All are medium-difficulty problems because the reduction step (sorting + insight) is non-obvious.