BeginnerArraysHashing
Two Sum
Problem
Given an array of integers nums and an integer target, return the indices of the two distinct elements whose values add up to target. You may assume exactly one valid answer exists, and you may not use the same element twice. The indices may be returned in any order.
Constraints
- 2 ≤ n ≤ 10^5
- -10^9 ≤ nums[i] ≤ 10^9
- -10^9 ≤ target ≤ 10^9
- exactly one valid pair exists
Examples
in: nums = [2,7,11,15], target = 9
out: [0,1]
nums[0] + nums[1] = 9.
in: nums = [3,3], target = 6
out: [0,1]
Two equal values at different indices are allowed.
What this tests
- Trading space for time with a hash map
- Asking the right clarifying questions (sorted? duplicates? indices or values?)
- Single-pass "look up the complement" reasoning
- Adapting the solution when the input properties change (sorted, streamed, many queries)
Problem ClarificationPattern RecognitionComplexity AnalysisCommunicationEdge Cases
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
The array is sorted. Can you avoid the extra memory?
F2
You will receive many queries with different
target values on the same array. How do you prepare?F3
Memory is extremely constrained and the array is unsorted. What do you do?
F4
The numbers arrive as a stream and you must report the first pair found. What changes?