Two Sum
Find two numbers in an array that add to a target
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to the target. You may not use the same element twice. Assume exactly one solution exists.
R — READ
READ
What exactly is this problem asking me to return?
Inputs: array of integers and a target integer. Output: indices of the two numbers. Constraint: each element used at most once.
Understanding of requirements and constraints. Can you clarify ambiguities?
Assuming without asking: Can I use an element twice? Should I return indices or values? What if no solution exists?
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] (because nums[0] + nums[1] = 2 + 7 = 9)
O — OBSERVE
OBSERVE
What patterns emerge from examples?
Work through small examples. Notice: if we've seen 2, and we need 9 − 2 = 7, we can check instantly if 7 is already stored.
Pattern recognition. Can you spot that a hash map enables O(1) lookup?
Skipping examples and jumping to a brute-force nested loop.
Example: [2, 7, 11, 15], target = 9
• i=0: num=2, complement=7. Is 7 in seen? No. Add 2→0.
• i=1: num=7, complement=2. Is 2 in seen? Yes at index 0. Return [0, 1].
P — PSEUDOCODE
PSEUDOCODE
What's my step-by-step plan?
Outline the algorithm without syntax. Hash map approach: store numbers as we iterate, check for complements.
Clear thinking and sound logic before coding.
Pseudocode that's too vague or already in code syntax.
1. Create an empty hash map (value → index)
2. For each index i and value num in the array:
a. Calculate complement = target − num
b. If complement in hash map, return [map[complement], i]
c. Add num → i to the hash map
3. If loop completes, no pair found
I — IMPLEMENT
IMPLEMENT
How do I translate the plan into clean code?
Write readable, correct Python. Handle edge cases (empty array, single element).
Syntax correctness, code clarity, and edge case handling.
Code that's hard to read or doesn't handle edge cases.
def twoSum(nums, target):
"""
Find two numbers in nums that add to target.
Args:
nums: List of integers
target: Target sum
Returns:
List of indices [i, j] where nums[i] + nums[j] == target
"""
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
T — TEST
TEST
Does my code work on all cases—typical, edge, and tricky?
Trace through test cases. Check typical cases, duplicates, and edge cases.
Thoroughness. Do you catch bugs before being told?
Testing only the happy path and missing edge cases.
Test 1: [2, 7, 11, 15], target=9 → [0, 1] ✓
Test 2: [3, 2, 4], target=6 → [1, 2] ✓
Test 3: [3, 3], target=6 → [0, 1] ✓
Test 4: [1, 2], target=3 → [0, 1] ✓
Test 5: [-1, 0, 1, 2], target=1 → [1, 2] (0 + 1 = 1) ✓
A — ANALYZE
ANALYZE
What's the complexity? Can I optimize further?
Count operations: one pass through array, O(1) hash operations on average.
Understanding of Big O notation and trade-offs.
Stating complexity without justifying it.
Why: We iterate through the array once (O(n)). For each element, hash map lookup and insertion are O(1) on average. We store up to n elements in the hash map (O(n) space).
Alternative approach: Brute force nested loop is O(n²) time, O(1) space. The hash map trade-off (more space, less time) is worth it for most interview settings.