← Create New Paste

3Sum in a Coding Interview: Sorting, Two Pointers and Skipping Duplicates

3 views
"Find all unique triplets in an array that sum to zero" is one of the most frequently asked medium coding interview problems. Most candidates know the idea; interviewers are really checking whether you handle duplicates correctly and can explain why the solution is O(n^2). From brute force to the standard solution The brute force checks every triple in O(n^3). A hash-set approach fixes one number and solves two-sum on the rest in O(n^2), but removing duplicate triplets becomes messy. The cleanest solution sorts the array first and uses two pointers. def three_sum(nums): nums.sort() res = [] n = len(nums) for i in range(n - 2): if nums[i] > 0: break # remaining numbers are all positive if i > 0 and nums[i] == nums[i - 1]: continue # skip duplicate first elements lo, hi = i + 1, n - 1 while lo < hi: s = nums[i] + nums[lo] + nums[hi] if s < 0: lo += 1 elif s > 0: hi -= 1 else: res.append([nums[i], nums[lo], nums[hi]]) lo += 1 hi -= 1 while lo < hi and nums[lo] == nums[lo - 1]: lo += 1 # skip duplicate second elements return res Why it works After sorting, for a fixed i the remaining range is sorted. If the sum is too small, only moving lo right can increase it; if too large, only moving hi left can decrease it. Each pair of pointers moves at most n steps, so each i costs O(n), and the whole algorithm is O(n^2) time with O(1) extra space besides the output (sorting may use O(log n) or O(n) depending on the language). The duplicate-handling details - Skip a first element equal to the previous one, otherwise the same triplets are produced again. - After recording a triplet, move lo past equal values. You do not need to skip hi separately, because the loop will move it when the sum becomes too large. - The early break when nums[i] > 0 is a small optimization worth mentioning. Trace an example For [-1, 0, 1, 2, -1, -4], sorting gives [-4, -1, -1, 0, 1, 2]. With i at -4, no pair reaches 4. With i at the first -1, the pointers find [-1, -1, 2] and [-1, 0, 1]. The second -1 is skipped. Result: two triplets. Common follow-ups 1. 3Sum Closest: track the sum with the smallest absolute difference from the target; same two-pointer loop. 2. 3Sum Smaller: count triplets with sum below a target; when the sum is small enough, all pairs between lo and hi count, so add hi - lo. 3. 4Sum and k-Sum: add another outer loop, or write a recursive k-sum that reduces to two-sum. 4. Can you do better than O(n^2)? For general inputs, no known algorithm is significantly faster in practice; saying this calmly is better than guessing. How to present it State the brute force, explain why sorting enables two pointers, write the code with the duplicate checks, then trace the example. Clear narration matters as much as the code. If you know the pattern but lose track of duplicate handling under pressure, Linkjob AI (https://linkjob.ai) offers real-time help during job interviews and technical interviews, so you can keep your explanation organized while you code.
Created Nov 17, 2026 11:28 Expires Nov 17, 2027 11:28