Do two sorted prices add up to a target?

Two pointers Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
a, t = [1, 3, 4, 6, 8, 11], 10
lo, hi, steps = 0, len(a) - 1, 0
while a[lo] + a[hi] != t:
    steps += 1
    if a[lo] + a[hi] < t:
        lo += 1
    else:
        hi -= 1
print(a[lo], a[hi], steps)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 4 6 4

Right: 1+11 too big, 1+8 too small, 3+8 too big, 3+6 too small, then 4+6 hits 10.

Each move discards exactly one value that cannot be in any pair, so four moves are enough here.

Why not the others?
  • B 4 6 3. Count the moves again: 3+6 = 9 also needs a move before 4+6.
  • C 3 8 2. 3 + 8 is 11, which is too big, so the sweep keeps going.
Pointers start at both ends of [1, 3, 4, 6, 8, 11]; each step shows the pair sum and which pointer moves, for targets 10 and 13.

Steps come from running the Python solution.

Text version

Target 10:

Cells: [1, 3, 4, 6, 8, 11]

  1. L = 0, R = 5. Sum = 12. 1 + 11 = 12, too big: move R
  2. L = 0, R = 4. Sum = 9. 1 + 8 = 9, too small: move L
  3. L = 1, R = 4. Sum = 11. 3 + 8 = 11, too big: move R
  4. L = 1, R = 3. Sum = 9. 3 + 6 = 9, too small: move L
  5. L = 2, R = 3. Sum = 10. 4 + 6 = 10: found

Result: true

Target 13:

Cells: [1, 3, 4, 6, 8, 11]

  1. L = 0, R = 5. Sum = 12. 1 + 11 = 12, too small: move L
  2. L = 1, R = 5. Sum = 14. 3 + 11 = 14, too big: move R
  3. L = 1, R = 4. Sum = 11. 3 + 8 = 11, too small: move L
  4. L = 2, R = 4. Sum = 12. 4 + 8 = 12, too small: move L
  5. L = 3, R = 4. Sum = 14. 6 + 8 = 14, too big: move R
  6. L = 3, R = 3. Pointers met: no pair

Result: false

30-second answer

Put one pointer at the cheapest item and one at the dearest. If the pair is too small, only a dearer low item can help, so move the low pointer up; if too big, move the high pointer down. Each step rules out one item for good, so the sweep is O(n) time and O(1) space.

Practise saying it · 60 s. No recording, just a timer

Explain the two-pointer pair check and why it is correct.

Say your answer out loud, then check which of these points you covered:

  • Pointers at both ends
  • Move the side that cannot help
  • O(n) time, O(1) space

Deep dive

Correctness: when the sum is too small, the low item cannot pair with anything (the high item is already the biggest left), so dropping it loses no answer. The mirror argument covers 'too big'.

A hash set also works in O(n) time but needs O(n) space and ignores the sorting you were given.

Binary search for each complement is O(n log n): correct, but slower than the sweep.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def has_pair(prices: list[int], target: int) -> bool:
    lo, hi = 0, len(prices) - 1
    while lo < hi:
        s = prices[lo] + prices[hi]
        if s == target:
            return True
        if s < target:
            lo += 1
        else:
            hi -= 1
    return False

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun hasPair(prices: List<Int>, target: Int): Boolean {
    var lo = 0
    var hi = prices.size - 1
    while (lo < hi) {
        val s = prices[lo] + prices[hi]
        when {
            s == target -> return true
            s < target -> lo++
            else -> hi--
        }
    }
    return false
}

Common mistakes

  • Moving both pointers on a mismatch, which can skip the answer.
  • Using lo <= hi, which lets one item pair with itself.

Senior take & follow-ups

The sweep is easy to write; the score comes from the one-sentence argument for why moving a pointer never skips a pair.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you count all such pairs?

    Show hint

    When the sum matches, count the run of equal values on each side, then move both pointers past them.

  2. What if the list is not sorted?

    Show hint

    Sort first (O(n log n)) or use a hash set (O(n) space).

See it animated on iPhone (Arrays in DSA Master - Data & Algorithms)

What each operation costs: Arrays · Array Operations

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.