Two-Sum and Its Many Variants
Solve two-sum, three-sum, four-sum, and two-sum with sorted array using hash maps and two pointers, comparing time and space costs.
Two-Sum and Its Many Variants is a free DSA 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 DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Two-Sum: The Classic Interview Problem
LeetCode 1 'Two Sum': given an unsorted array and a target, return the indices of two elements that add up to the target. The brute-force O(n²) approach checks all pairs. The optimal O(n) approach uses a hash map: for each element x, check if target - x already exists in the map. If yes, return the pair of indices. If no, store x and its index in the map.
Two-sum is often the very first problem in an interview — knowing it cold signals that you are ready to move to harder problems.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Why the Hash Map Works for Two-Sum
The hash map stores every element seen so far. When processing element x, if target - x is in the map, those two elements form a valid pair. Crucially, the complement is always checked before x is stored, preventing the case where a single element is paired with itself (e.g., if x == target/2, the map check happens before x is stored, so it won't match unless there are two copies).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iTwo-Sum on a Sorted Array (Two Pointers)
If the array is already sorted and you need indices of the values (not the original indices), use the two-pointer technique: left and right pointers starting at opposite ends. If sum equals target, return. If sum is too small, move left right. If sum is too large, move right left. This is O(n) time and O(1) space — better than the hash map approach when the array is sorted and memory is constrained.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Three-Sum (LeetCode 15)
LeetCode 15 'Three Sum': find all unique triplets summing to zero. Sort the array, fix one element at a time, and apply two-pointer on the remaining sorted subarray. Skip duplicate values to avoid duplicate triplets. Time: O(n²) — optimal for this problem since the output itself can have O(n²) triplets.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Four-Sum (LeetCode 18)
LeetCode 18 'Four Sum': find all unique quadruplets summing to target. Extend three-sum: fix two elements with two nested loops (skipping duplicates), then apply two-pointer on the inner subarray. Time: O(n³). For k-sum in general, the pattern recurse k-2 times then apply two pointers, giving O(n^(k-1)) time.
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Two-Sum Closest to Target
A common variant: find the pair with sum closest to target (may not equal target exactly). Sort the array and use two pointers. Track the closest sum seen so far and update it whenever you find a pair with a smaller absolute difference from the target. This O(n log n) approach is straightforward after sorting.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Two-Sum with Multiple Pairs (All Pairs)
To find all pairs summing to a target: sort the array and use two pointers, collecting all pairs. After finding a valid pair, skip duplicates from both ends before continuing. This gives O(n log n) for sorting plus O(n) for the scan — O(n log n) overall. Using a hash map to collect pairs is also valid but requires care around duplicates.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Count Pairs with Sum Less Than K
Another variant: count how many pairs have a sum less than k. Sort the array, use two pointers. When nums[lo] + nums[hi] < k, all pairs (lo, lo+1), (lo, lo+2), ..., (lo, hi) are valid — that is hi - lo pairs. Advance lo. Otherwise shrink hi. Total time: O(n log n) for sorting plus O(n) for counting.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyTwo-Sum with Hash Map: Handling Duplicates
When the same value can appear multiple times and you need count of valid pairs (not just existence), store frequency counts in the map. For pairs where both elements are equal, the count of pairs from frequency f is f*(f-1)//2. For pairs where the two elements differ, multiply their frequencies. This allows counting all valid pairs in O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Recognising Two-Sum Pattern Variations
The two-sum pattern appears in many disguises. Recognise it when a problem asks to find two or more elements satisfying a numeric relationship (sum, product, difference). The core strategy is always: fix one element, then find its complement in a precomputed structure (hash map or sorted array + pointer). Extend to k-sum by fixing k-2 elements with nested loops and applying the base case.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Interview Communication for Two-Sum
When two-sum appears in an interview, walk through your thinking aloud: 'I need two numbers that add to target. For each number x I need to check if target-x exists. I can answer that in O(1) with a hash map, giving O(n) total time and O(n) space. Alternatively, if the array were sorted, I could use two pointers in O(1) space.' State both approaches and ask if there are space constraints before choosing.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: two-sum uses a hash map to check complement existence in O(1), giving O(n) overall, for sorted arrays two pointers achieve O(1) space, and three-sum and four-sum reduce to two-sum via sorting and nested loops, running in O(n²) and O(n³) respectively. Next up we explore frequency counting patterns and grouping with defaultdict and Counter.
Frequently asked questions
Is the “Two-Sum and Its Many Variants” lesson free?
Yes — the full text of “Two-Sum and Its Many Variants” is free to read here on the web, and the DSA 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 DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Two-Sum and Its Many Variants”?
Solve two-sum, three-sum, four-sum, and two-sum with sorted array using hash maps and two pointers, comparing time and space costs. You practise DSA 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 DSA Interview Prep?
No prior experience is required. DSA 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 “Two-Sum and Its Many Variants” 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 DSA Interview Prep lesson?
Yes. Every DSA 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.