Coding interview problems › Two Pointers

↔️ Two Pointers Medium

Two Sum II (Sorted Array)

Two Sum II on a sorted array explained: two pointers from both ends find the pair in O(n) time and O(1) space, why it never skips the answer, tested Python.

Also searched as: two sum sorted array two pointers · pair sum in sorted array

↔️

Try it live Free

Two Pointers

Watch two pointers turn an O(n²) double loop into one sweep, always moving the pointer that cannot be part of a better answer. Pair-sum on a sorted array uses exactly that rule.

Open the playground →

The problem

A list of integers is sorted in non-decreasing order. Find two different positions whose values add up to target and return their indices 1-based. Exactly one answer exists, and you should use only constant extra space.

Inputnumbers = [2, 7, 11, 15], target = 9
Output[1, 2]
Inputnumbers = [-1, 0], target = -1
Output[1, 2]

The key insight

Because the list is sorted, put one pointer on the smallest value and one on the largest. If their sum is too big, the only way to shrink it is to move the right pointer left; if too small, move the left pointer right. Each move throws away a value that cannot be part of any answer, so you never skip the real pair.

Brute force first: Checking every pair is O(n²); binary searching the partner for each element is O(n log n).

Step-by-step approach

  1. Set i = 0 and j = n - 1.
  2. Compute s = numbers[i] + numbers[j].
  3. If s == target, return [i + 1, j + 1].
  4. If s < target, move i right; otherwise move j left.
  5. Repeat while i < j.

Python solution

PYTHON 3tested
def two_sum_sorted(numbers, target):
    i, j = 0, len(numbers) - 1
    while i < j:
        s = numbers[i] + numbers[j]
        if s == target:
            return [i + 1, j + 1]      # 1-based indices
        if s < target:
            i += 1                     # need a bigger sum
        else:
            j -= 1                     # need a smaller sum
    return []

Complexity

TimeO(n)
SpaceO(1)

Each iteration moves one pointer inward, so there are at most n - 1 iterations. Only two indices are stored.

Common mistakes

Frequently asked questions

What is the time and space complexity of Two Sum II?

O(n) time and O(1) space with two pointers. Binary search for each partner is O(n log n).

Why is it safe to discard numbers[j] when the sum is too big?

numbers[i] is the smallest value still available, and even with it the sum is too big. Every other partner for numbers[j] is at least as big, so numbers[j] cannot be in any answer.

How does this extend to 3Sum?

Fix one element, then run this two-pointer search on the rest for the remaining target. That gives O(n²) for 3Sum.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Two Pointers Two Pointers lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.