Pair with a given sum

Lesson 2.2 · Easy · Opposite ends · 6 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

In a sorted array, find two numbers that add up to the target.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

L10

313

324

335

366

397

408

429

5010

5111

5412

5613

5814

R5915

1 + 59 = 60. Too small. Move L right to get a bigger number.

sum 60 · target 65

1 / 15

The idea

Complexity

Time	Space	Why
`O(n)`	`O(1)`	Each step moves one pointer inward (O(n log n) if you must sort first).

In Python

def pair_sum(nums, target):        # nums is sorted
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target: return [l, r]
        if s < target: l += 1      # need more
        else: r -= 1               # need less

Try it on LeetCode: Two Sum II - Input Array Is Sorted →

Summary: say it in the interview

Put L at the smallest and R at the largest. If the sum is too small, only moving L right can raise it. If too big, only moving R left can lower it. Each move rules out a whole row of pairs.
Time O(n), space O(1). Each step moves one pointer inward (O(n log n) if you must sort first).