Two Sum and Its Variants: Answering the Interview Follow-Ups

Two Sum and Its Variants: Answering the Interview Follow-Ups

Linkjob AI

Two Sum is often the first problem in a coding interview, and interviewers rarely stop at the basic version. Knowing its family of variants lets you answer the follow-ups calmly instead of starting from scratch each time.

1. The classic: unsorted array, return indices

Walk the array once with a hash map from value to index. For each number x, check whether target - x is already in the map. If yes, you're done; if not, store x. That's O(n) time and O(n) space. Say why you check before inserting: it prevents using the same element twice.

2. Sorted array: two pointers

If the input is sorted, start one pointer at each end. If the sum is too small, move the left pointer right; if too large, move the right pointer left. O(n) time and O(1) extra space, which is the point the interviewer wants you to make.

3. Count all pairs, or return unique pairs

Counting pairs: keep a frequency map and add the count of target - x before recording x. Unique pairs: sort, use two pointers, and skip duplicates after each match. Ask which one they want, because the duplicate handling differs.

4. Three Sum and k-Sum

Sort, fix one number, then run the two-pointer Two Sum on the rest. That gives O(n squared) for Three Sum. Generalize recursively for k-Sum. Skipping duplicate values for the fixed element is the bug most candidates hit.

5. Two Sum in a binary search tree or a data stream

For a BST, an in-order traversal gives a sorted sequence, so two pointers (or a hash set during traversal) works. For a stream with add and find operations, discuss the trade-off: a hash map makes add O(1) and find O(n), while maintaining a sorted list flips the costs.

How to present it

  • State brute force O(n squared) first, then improve
  • Ask: sorted? duplicates? exactly one answer? indices or values?
  • Test with negatives, zeros, and a pair of equal numbers

Practising these follow-ups out loud is what makes them feel easy on the day. If you want a mock interviewer that pushes on variants, the Linkjob AI app is one option (disclosure: this guide is published by the Linkjob AI team).

Report Page