Competitive Programming Academy · Lesson

Find a Pair with a Given Sum

Beat the O(n^2) brute force.

The Pair-Sum Problem

Given an array and a target, find two values that add up to it. It is one of the most common warm-up tasks in contests. 🔍

The obvious fix tries every pair with two nested loops. It works, but checking all pairs costs O(n^2) and can be far too slow.

for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == target:
            return (i, j)