Find a Pair with a Given Sum
Beat the O(n^2) brute force.
Find a Pair with a Given Sum is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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 Brute-Force Way
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)Where Brute Force Breaks
With n near 100000, O(n^2) is ten billion checks and you will hit a TLE. The constraints are telling you to find something faster.
Sort, Then Sweep
If you sort the array first, two pointers from both ends solve it in one pass. Sorting costs O(n log n), then the sweep is O(n).
a.sort()
left, right = 0, len(a) - 1Compare to the Target
Each step, read a[left] + a[right]. That single number decides your next move with no guessing involved.
total = a[left] + a[right]Exact Match: Done
If the sum equals the target, you have found the pair. Return it right away since you only need one valid answer.
if total == target:
return (left, right)Otherwise, Adjust
If the sum is too small move left rightward; if too big move right leftward. Sorted order guarantees each move helps.
elif total < target:
left += 1
else:
right -= 1No Pair Exists
If the pointers cross without a match, no valid pair exists. The loop ending is itself a complete answer.
The Hash-Set Alternative
If you must keep original indices, a hash set is cleaner: for each value, check if target minus it was already seen.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Choosing Your Method
Use two pointers when the array is or can be sorted; use the hash set when you need true O(n) without sorting or must keep indices.
Watch for Duplicates
If a value can pair with itself, make sure your two indices differ. A quick left != right or i != j check avoids that trap.
Quick Check
You want to beat the O(n^2) brute force for finding a pair that sums to a target.
Recap
Sort then sweep with two pointers to find a target pair in O(n log n), or use a hash set for O(n) when indices matter. Pick by the constraints. ✅
Frequently asked questions
Is the “Find a Pair with a Given Sum” lesson free?
Yes — the full text of “Find a Pair with a Given Sum” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Find a Pair with a Given Sum”?
Beat the O(n^2) brute force. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Find a Pair with a Given Sum” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Two Pointers on a Sorted Array
- Find a Pair with a Given Sum
- Remove Duplicates In Place
- Merge Two Sorted Sequences