How to Solve: Two Sum (All Variations) – Complete Guide for FAANG Interviews

How to Solve: Two Sum (All Variations) – Complete Guide for FAANG Interviews

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—master it, and you prove you can break down problems, optimize trade-offs, and handle edge cases like a senior engineer."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you understand: 1. Hash Maps (Dictionaries) – O(1) average-time lookups, insertions, and deletions. 2. Two-Pointer Technique – Efficiently traverse sorted arrays by adjusting pointers based on conditions. 3. Prefix Sums – Track cumulative sums to solve subarray problems in linear time.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Run this checklist for every Two Sum variation:

1. Clarify the Problem
2. Are duplicates allowed? (e.g., [3,3] with target 6 → valid?)
3. Is the input sorted? (If not, can we sort it?)
4. Do we need all solutions or just one?

5. Are indices required, or just values?

6. Choose the Right Technique

7. Unsorted, single solution? → Hash map (O(n) time, O(n) space).
8. Sorted input? → Two-pointer (O(n) time, O(1) space).
9. Subarray sum? → Prefix sum + hash map.

10. All possible pairs? → Backtracking or sorting + two-pointer.

11. Handle Edge Cases

12. Empty input.
13. No solution (return [] or -1).
14. Duplicate values (e.g., [3,3] with target 6).

15. Negative numbers (common in subarray problems).

16. Optimize for Time/Space

17. Can we reduce space? (e.g., two-pointer instead of hash map).

18. Can we avoid sorting? (e.g., hash map for unsorted input).

19. Write Pseudocode First

20. Sketch the logic before coding (e.g., "For each num, check if target - num exists in map").

21. Code with Clean Variables

22. Use descriptive names (e.g., complement instead of x).

23. Avoid nested loops unless necessary (e.g., for "Three Sum").

24. Test with Examples

25. Run through 2-3 test cases (including edge cases).
26. Verify time/space complexity.

? WORKED EXAMPLES

Example 1 – Basic: Two Sum (LeetCode 1)

Problem: Given an array of integers nums and an integer target, return indices of the two numbers that add up to target. Assume exactly one solution exists.

Framework Application: 1. Clarify: Unsorted, one solution, return indices. 2. Technique: Hash map (store num → index). 3. Edge Cases: No solution (but problem guarantees one), duplicates (e.g., [3,3]). 4. Optimize: Single pass (O(n) time, O(n) space). 5. Pseudocode:
map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in map:
return [map[complement], i]
map[num] = i 6. Code (Python):
python
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return [] # Shouldn't reach here per problem statement 7. Complexity:
- Time: O(n) (single pass).
- Space: O(n) (hash map storage). 8. Why This Works:
- The hash map stores each number’s index as we iterate.
- For each num, we check if its complement (target - num) exists in the map.
- If found, we return the stored index and current index.

Example 2 – Medium: Two Sum II (LeetCode 167)

Problem: Given a 1-indexed sorted array numbers and a target, return the indices of the two numbers that add up to target. Assume exactly one solution exists.

Twist: Input is sorted, so we can optimize space.

Framework Application: 1. Clarify: Sorted, one solution, return 1-indexed indices. 2. Technique: Two-pointer (O(n) time, O(1) space). 3. Edge Cases: No solution (but problem guarantees one), duplicates (e.g., [2,2,3,4]). 4. Optimize: No extra space (unlike hash map). 5. Pseudocode:
left = 0, right = len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left + 1, right + 1] # 1-indexed
elif current_sum < target:
left += 1
else:
right -= 1 6. Code (Python):
python
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
elif current_sum < target:
left += 1
else:
right -= 1
return [] # Shouldn't reach here 7. Complexity:
- Time: O(n) (single pass).
- Space: O(1) (no extra space). 8. Why This Works:
- Since the array is sorted, we can use two pointers:
- If sum < target, move the left pointer right (to increase sum).
- If sum > target, move the right pointer left (to decrease sum).
- Guaranteed to find the solution in O(n) time.

Example 3 – Hard: Subarray Sum Equals K (LeetCode 560)

Problem: Given an array nums and an integer k, return the total number of subarrays whose sum equals k.

Twist: Requires prefix sums and a hash map to track frequencies.

Framework Application: 1. Clarify: Unsorted, may have negatives, return count of subarrays. 2. Technique: Prefix sum + hash map (O(n) time, O(n) space). 3. Edge Cases: Empty array, no subarrays (return 0), k = 0. 4. Optimize: Single pass with prefix sum tracking. 5. Pseudocode:
prefix_sum = 0
count = 0
map = {0: 1} # Initialize with prefix_sum 0 (empty subarray)
for num in nums:
prefix_sum += num
if (prefix_sum - k) in map:
count += map[prefix_sum - k]
map[prefix_sum] = map.get(prefix_sum, 0) + 1
return count 6. Code (Python):
python
def subarraySum(nums, k):
prefix_sum = 0
count = 0
prefix_map = {0: 1} # To handle subarrays starting from index 0
for num in nums:
prefix_sum += num
if (prefix_sum - k) in prefix_map:
count += prefix_map[prefix_sum - k]
prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
return count 7. Complexity:
- Time: O(n) (single pass).
- Space: O(n) (hash map storage). 8. Why This Works:
- prefix_sum tracks the cumulative sum up to the current index.
- If prefix_sum - k exists in the map, it means there are subarrays ending at the current index that sum to k.
- The map stores the frequency of each prefix_sum to count all valid subarrays.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Two Sum problems come in three flavors: 1. Basic (unsorted, one solution): Use a hash map to store complements in O(n) time. 2. Sorted input: Two-pointer for O(1) space. 3. Subarrays or all solutions: Prefix sums or backtracking.

Before coding, ask: Is the input sorted? Do I need all solutions? Are duplicates allowed? Then pick your technique. For unsorted, hash map. For sorted, two-pointer. For subarrays, prefix sums. Test edge cases like empty input or duplicates. And if the interviewer asks for a follow-up, think: Can I sort? Can I use a set? Can I optimize space?

You’ve got this. Now go crush that interview." ?