#1 Two Sum
frequently reported atGoogleAmazonMicrosoftAdobeBloombergInfosys
the problem
In plain words
Given an array of integers and a target, return the indices of the two numbers that add up to the target. Exactly one answer exists, and you may not use the same element twice.
in nums = [2,7,11,15], target = 9
out [0,1]
2 + 7 = 9.
in nums = [3,2,4], target = 6
out [1,2]
in nums = [3,3], target = 6
out [0,1]
- 2 ≤ n ≤ 10⁴
- -10⁹ ≤ nums[i], target ≤ 10⁹
- Exactly one valid answer
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternHash lookup (seen before?)
For each x, the only partner that works is target − x. A HashMap answers "have I already seen it, and where?" in O(1).
solutions
From brute force to optimal
Try all i < j.
- For each i, for each j > i, test nums[i] + nums[j] == target (add as
long, a safe habit).
n(n−1)/2 pairs.
Only two indices.
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { // every pair once if ((long) nums[i] + nums[j] == target) return new int[] {i, j}; // long: no overflow } } return new int[0]; // the problem guarantees an answer }}Dry run
Sort an array of indices by value, so the original positions survive the sort, then converge two pointers.
- order = indices sorted by nums[index].
- left = 0, right = n−1.
- Sum too small → left++; too big → right--.
The sort dominates; the scan is O(n).
The index array (boxed Integer for the comparator).
class Solution { public int[] twoSum(int[] nums, int target) { Integer[] order = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) order[i] = i; Arrays.sort(order, (a, b) -> Integer.compare(nums[a], nums[b])); // sort indices by value int left = 0, right = nums.length - 1; while (left < right) { long sum = (long) nums[order[left]] + nums[order[right]]; // long: no overflow if (sum == target) return new int[] {order[left], order[right]}; if (sum < target) left++; else right--; } return new int[0]; }}First map every value to its index, then look up each complement.
- Pass 1: indexOf.put(nums[i], i).
- Pass 2: j = indexOf.get(target − nums[i]); answer if j exists and j ≠ i.
Two linear passes with O(1) average lookups.
The map holds up to n values.
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> indexOf = new HashMap<>(); for (int i = 0; i < nums.length; i++) indexOf.put(nums[i], i); // last index wins for (int i = 0; i < nums.length; i++) { Integer j = indexOf.get(target - nums[i]); if (j != null && j != i) return new int[] {i, j}; // never pair an element with itself } return new int[0]; }}Look up the complement first, then store the current number.
- need = target − nums[i].
- If need is in the map → return [map.get(need), i].
- Else store nums[i] → i.
Each element: one lookup and one insert, O(1) average.
Up to n entries in the map.
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> seen = new HashMap<>(); // value → index for (int i = 0; i < nums.length; i++) { int need = target - nums[i]; Integer j = seen.get(need); if (j != null) return new int[] {j, i}; seen.put(nums[i], i); // store AFTER the lookup } return new int[0]; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify: return indices, not values? Exactly one answer? Can the same value appear twice? (Yes: [3,3].)
- State the brute force in one line, then: "For each x I need target − x. A HashMap tells me in O(1) whether I've seen it."
- Point out why you look up before storing: an element can't pair with itself.
traps
- Storing before looking up (pairs 3 with itself for target 6).
- Sorting the values directly: the original indices are lost.
int j = map.get(need)throws a NullPointerException when the key is missing. Keep it as anInteger(or usecontainsKey).
what they ask next
Follow-ups
What if the array is sorted?
Two Sum II (LC 167): two pointers, O(n) time and O(1) space.
What if you need all pairs, or the number of pairs?
Keep counts in the map: at each x, add count[target − x] to the answer, then increment count[x].
Three numbers (3Sum, LC 15)?
Sort, fix one number, run two pointers on the rest: O(n²).
before you submit
Edge cases to test
- The same value twice ([3,3], target 6) → [0,1].
- Zeros and negatives ([0,4,3,0], target 0 → [0,3]).
- An element must not pair with itself ([3,2,4], target 6 → [1,2], not [0,0]).
- Values near ±10⁹: the sum of two of them overflows
int— the map approach only ever subtracts, but a pair check should add aslong.
practise next
Similar problems
- #167Two Sum II - Input Array Is SortedMediumin Two Pointers
- #153SumMediumin Two Pointers
- #560Subarray Sum Equals KMediumin Hashing