Two Sum to 4Sum: How the Hashing and Two-Pointer Ideas Scale

You solve the k-sum family by reducing the problem to a simpler version you already know. Two Sum uses a hashmap for O(n) time, while 3Sum and 4Sum rely on sorting and two-pointers to keep the complexity at O(n^2) and O(n^3) respectively. Stop trying to find a magic formula and start nesting your loops correctly.

The Two Sum baseline

When you have an array like [2, 7, 11, 15] and a target of 9, you need to find two indices that add up to that value. If you use a nested loop, you check every pair, which takes O(n^2) time. A hashmap changes this. You iterate through the array once, storing each number and its index in the map. For each x, you check if target - x exists in the map. This lookup is O(1), making the total time O(n). This is the fastest way to solve Two Sum because you trade space for speed.

Moving to sorted arrays

If the array is already sorted, you do not need a hashmap. You place one pointer at the start and one at the end. If the sum of arr[left] and arr[right] is less than the target, you increment left to increase the sum. If it is greater, you decrement right. This is the two-pointer technique. It runs in O(n) time with O(1) extra space. This is the foundation for solving 3Sum and 4Sum.

Scaling to 3Sum and 4Sum

For 3Sum, you fix one element arr[i] and then solve the remaining 2Sum problem on the subarray arr[i+1...n-1] using the two-pointer approach. Since the 2Sum part takes O(n) and you do it for each of the n elements, the total complexity is O(n^2).

For 4Sum, you fix two elements arr[i] and arr[j] and solve the remaining 2Sum problem on the rest of the array. This adds another loop, pushing the complexity to O(n^3). You cannot avoid this growth because you are essentially picking k-2 elements and searching for the rest.

A worked example

Consider the array [-1, 0, 1, 2, -1, -4] and target 0 for 3Sum.

1. Sort the array: [-4, -1, -1, 0, 1, 2].
2. Fix i = 0 (value -4). You need two numbers that sum to 4 in the range [-1, -1, 0, 1, 2].
3. Set left = 1 (value -1) and right = 5 (value 2). Sum is 1. Too small, move left to 2.
4. Now left = 2 (value -1) and right = 5 (value 2). Sum is 1. Still too small.
5. Continue this until you exhaust the array for i = 0, then move to i = 1.

Handling duplicates

In 3Sum and 4Sum, you must skip duplicate values to avoid redundant triplets or quadruplets. If arr[i] == arr[i-1], just continue to the next iteration. Do the same inside your two-pointer logic. If arr[left] == arr[left+1], increment left again. This keeps your output clean and prevents your code from counting the same set of indices multiple times.

The k-sum rule of thumb

• Use a hashmap for 2Sum if the array is unsorted and you have extra memory.
• Use two-pointers for 2Sum if the array is sorted or memory is tight.
• For k > 2, sort the array first and fix k-2 elements with nested loops.
• Always skip duplicates by checking arr[i] == arr[i-1] to ensure unique results.
• Practice these on DSA Tracker to see how the loop nesting changes as k increases.

Next step: Write a function that solves 3Sum without using a hashmap, then modify it to solve 4Sum by adding one extra outer loop.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Hash tables on Wikipedia.