Two Pointers Pattern — Template, Examples & When to Use It

Q: When should I use two pointers instead of a hash map?

Use two pointers when the array is sorted or can be sorted, and you need O(1) extra space. Use a hash map when the input is unsorted and the answer depends on original indices — that is why LeetCode's Two Sum is a hash-map problem while Two Sum II, which promises sorted input, is the two-pointer one.

Q: Why does moving one pointer not skip a valid answer?

Because the array is sorted. If the current sum is too small, every pair using the current left with a smaller right is also too small, so all of them can be discarded at once — left is the only pointer whose move can help. The argument is symmetric when the sum is too large. Without sorting, that reasoning collapses and the pattern is unsound.

Q: Is 3Sum O(n²) or O(n³)?

O(n²). The outer loop fixes one anchor in O(n) and the inner two-pointer scan is O(n), which is O(n²) total — the sort's O(n log n) is dominated. The brute force over all triples is the O(n³) version.

Two pointers is the pattern behind almost every "find a pair/triple that sums to X" question, and it is the one people most often half-know: they can recite the 2Sum solution but cannot say why moving a pointer is safe, which is the part interviewers probe.

The idea

Put left at the start of a sorted array and right at the end. Look at the pair. Because the array is sorted, the comparison tells you which pointer to move:

sum too small → the only way to grow it is left += 1
sum too large → the only way to shrink it is right -= 1

Each move discards a whole set of pairs in one step, and that is where the speedup comes from. Moving left past index i rules out every pair (i, j) for j <= right at once, because all of them are smaller than a sum already too small.

Sum too small? Only left can help. Too large? Only right. Each move discards a whole block of pairs.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int total = nums[left] + nums[right];
        if (total == target) return new int[] { left, right };
        if (total < target) left++;
        else right--;
    }
    return new int[0];
}

vector<int> twoSumSorted(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        int total = nums[left] + nums[right];
        if (total == target) return {left, right};
        if (total < target) left++;
        else right--;
    }
    return {};
}

/* Writes the two indices into out; returns 1 on success, 0 otherwise. */
int twoSumSorted(int* nums, int n, int target, int out[2]) {
    int left = 0, right = n - 1;
    while (left < right) {
        int total = nums[left] + nums[right];
        if (total == target) {
            out[0] = left; out[1] = right;
            return 1;
        }
        if (total < target) left++;
        else right--;
    }
    return 0;
}

function twoSumSorted(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const total = nums[left] + nums[right];
    if (total === target) return [left, right];
    if (total < target) left++;
    else right--;
  }
  return [];
}

When to reach for it

The input is sorted, or sorting it does not destroy what the question asks for.

Sorting costs O(n log n) and is almost always worth it to reach an O(n) scan — but it is fatal if the answer must preserve original indices, which is exactly why LeetCode's unsorted Two Sum is a hash-map problem and not this one.

You are looking for a pair or a small tuple satisfying a monotone condition — a

sum, a difference, a product.

Or you are partitioning in place: read pointer scanning forward, write pointer

marking where the next kept element goes. Remove Duplicates, Move Zeroes and Sort Colors are all this shape.

The template

def converge(nums, target):
    nums.sort()                     # the enabling step
    left, right = 0, len(nums) - 1
    while left < right:
        value = f(nums[left], nums[right])
        if value == target:
            record(left, right)
            left += 1               # advance BOTH on a hit, or you loop forever
            right -= 1
        elif value < target:
            left += 1
        else:
            right -= 1

void converge(int[] nums, int target) {
    Arrays.sort(nums);                    // the enabling step
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int value = f(nums[left], nums[right]);
        if (value == target) {
            record(left, right);
            left++;                       // advance BOTH on a hit
            right--;
        } else if (value < target) {
            left++;
        } else {
            right--;
        }
    }
}

void converge(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());       // the enabling step
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        int value = f(nums[left], nums[right]);
        if (value == target) {
            record(left, right);
            left++;                       // advance BOTH on a hit
            right--;
        } else if (value < target) {
            left++;
        } else {
            right--;
        }
    }
}

function converge(nums, target) {
  nums.sort((a, b) => a - b);        // the enabling step — NOT the default sort
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const value = f(nums[left], nums[right]);
    if (value === target) {
      record(left, right);
      left++;                        // advance BOTH on a hit
      right--;
    } else if (value < target) {
      left++;
    } else {
      right--;
    }
  }
}

Worked example: 3Sum

3Sum is the reason this pattern is worth learning properly: it is two pointers wrapped in

a loop, and the whole difficulty is the duplicate handling.

def three_sum(nums):
    nums.sort()
    out = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                      # skip a repeated anchor
        if nums[i] > 0:
            break                         # sorted: no triple can reach 0 from here
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                out.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1             # skip repeated seconds
    return out

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> out = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // repeated anchor
        if (nums[i] > 0) break;                          // cannot reach 0

        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total < 0) {
                left++;
            } else if (total > 0) {
                right--;
            } else {
                out.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
            }
        }
    }
    return out;
}

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> out;

    for (int i = 0; i + 2 < (int)nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // repeated anchor
        if (nums[i] > 0) break;                          // cannot reach 0

        int left = i + 1, right = (int)nums.size() - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total < 0) {
                left++;
            } else if (total > 0) {
                right--;
            } else {
                out.push_back({nums[i], nums[left], nums[right]});
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
            }
        }
    }
    return out;
}

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const out = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;   // repeated anchor
    if (nums[i] > 0) break;                           // cannot reach 0

    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const total = nums[i] + nums[left] + nums[right];
      if (total < 0) {
        left++;
      } else if (total > 0) {
        right--;
      } else {
        out.push([nums[i], nums[left], nums[right]]);
        left++;
        right--;
        while (left < right && nums[left] === nums[left - 1]) left++;
      }
    }
  }
  return out;
}

Sorting is what makes both the duplicate skip and the nums[i] > 0 early exit possible. Say that out loud in an interview — it shows you know sorting bought you more than ordering.

Two pointers vs sliding window

Both use two indices, and people conflate them.

	Two pointers	Sliding window
Direction	Converging, from both ends	Same direction, left trails right
Input	Usually sorted	Order matters, sorting would break it
Tracks	The pair at the ends	State for everything inside the range
Answers	Pairs, triples, in-place partitions	Best/shortest/longest contiguous run

Complexity

O(n log n) dominated by the sort, or O(n) if the input arrives sorted. The scan itself is O(n) — each pointer only moves inward, so together they take at most n steps. 3Sum is O(n²): an O(n) scan inside an O(n) loop. Space is O(1) beyond the sort.

Mistakes that cost the round

Sorting when indices matter. If the answer is a list of original positions, sorting

destroys it. Pair values with their indices first, or use a hash map instead.

Not advancing both pointers on a hit. left += 1 alone on an exact match re-finds

the same sum forever on inputs with duplicates.

Forgetting the duplicate skips in 3Sum. The naive version returns [-1,0,1] three

times on [-1,-1,0,0,1,1]. Deduping the output afterwards works but is the answer that gets follow-up questions.

`left <= right` instead of `left < right`. Lets an element pair with itself.

What to drill

Two Sum II — Input Array Is Sorted — the bare pattern.
Valid Palindrome — converging pointers on a string.
Container With Most Water — the greedy move argument, which is the same reasoning.
Remove Duplicates from Sorted Array — the read/write partition variant.
3Sum — the one that gets asked.
Trapping Rain Water — two pointers plus running maxima; the hard version.

All six are on the 22 DSA Patterns sheet.

Frequently asked

When should I use two pointers instead of a hash map?

Use two pointers when the array is sorted or can be sorted, and you need O(1) extra space. Use a hash map when the input is unsorted and the answer depends on original indices — that is why LeetCode's Two Sum is a hash-map problem while Two Sum II, which promises sorted input, is the two-pointer one.

Why does moving one pointer not skip a valid answer?

Because the array is sorted. If the current sum is too small, every pair using the current left with a smaller right is also too small, so all of them can be discarded at once — left is the only pointer whose move can help. The argument is symmetric when the sum is too large. Without sorting, that reasoning collapses and the pattern is unsound.

Is 3Sum O(n²) or O(n³)?