How to Solve Two Sum and Its Variations

Given an array of numbers and a target value, find two numbers in the array that add up to the target. The naive approach of checking every pair takes quadratic time. There are much faster approaches using a Hash Map or Two Pointers.

Create an empty Hash Map. Iterate through the array. For each element, calculate the complement by subtracting the element from the target. Check if the complement already exists in the Hash Map. If it does, you have found your pair. If not, add the current element and its index to the Hash Map and continue.

For every element you visit, you are asking whether the number needed to complete the pair has been seen before. The Hash Map gives you that answer in constant time, bringing the total time complexity down to linear.

If the array is sorted, use two pointers. Place one pointer at the very beginning and one at the very end. Calculate the sum of the two elements. If the sum equals the target, you found the pair. If the sum is less than the target, move the left pointer right. If the sum is greater, move the right pointer left.

Three Sum asks for triplets that add to zero. Sort the array first. Fix one element by iterating through the array. For the remaining elements to the right of the fixed element, apply the Two Pointer technique to find pairs that sum to the negative of the fixed element.

After finding a valid triplet, skip duplicate values for all three pointers. If the fixed element is the same as the previous one, skip it. After the two pointers find a match, advance both pointers and skip any repeating values to avoid duplicate triplets in the result.

Four Sum extends the same pattern. Fix two elements using two nested loops and apply Two Pointers for the remaining two. The pattern generalizes: for K Sum, fix K minus two elements with nested loops and use Two Pointers for the final two. Each additional fixed element adds one more level of iteration.