These are the notes for DSA episode 2. Two Sum is LeetCode problem 1 and one of the most asked interview questions. It teaches the most useful trick in DSA: hashing, trading a little memory for instant lookups. You will see the brute force, watch it time out, invent the complement-plus-HashMap idea, and write the one-pass solution. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Your aunt gives you a ₹500 gift card. The shop gives no change, and you want exactly two items whose prices add up to exactly ₹500. The online store has 2 lakh products. Which two?
Problem statement
Given an integer array nums and an integer target, return the indexes of the two numbers that add up to target.
- You may not use the same element twice.
- Assume exactly one answer exists (we return
[-1, -1]if none does). - Constraints:
2 ≤ n ≤ 10⁵, values and target fit in anint.
| nums | target | answer | why |
|---|---|---|---|
| [2, 7, 11, 15] | 9 | [0, 1] | 2 + 7 = 9 |
| [3, 2, 4] | 6 | [1, 2] | 2 + 4 = 6 (not 3 + 3: same element) |
| [3, 3] | 6 | [0, 1] | two different elements with the same value |
Brute force: try every pair
import java.util.*;
public class Main {
static int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] + nums[j] == target) return new int[]{i, j};
return new int[]{-1, -1};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
System.out.println(Arrays.toString(twoSum(new int[]{3, 2, 4}, 6)));
}
}
Output:
[0, 1]
[1, 2]
Correct. In an interview, always state the brute force first: it shows you understand the problem.
Watching it time out
300,000 prices 0, 2, 4, 6, ... with the target equal to the sum of the last two, so the only answer is at the very end (the worst case):
int n = 300000, nums[] = new int[n];
for (int i = 0; i < n; i++) nums[i] = 2 * i;
long t = System.nanoTime();
int[] ans = twoSum(nums, nums[n - 2] + nums[n - 1]);
System.out.println(Arrays.toString(ans) + " " + (System.nanoTime() - t) / 1000000 + " ms");
Time Limit Exceeded (8 s)
Why it is slow
- There are
n(n-1)/2pairs: O(n²). For n = 300,000 that is about 45 billion pairs. - Look at the inner loop: when we stand at
nums[i], we are searching for exactly one number,target - nums[i], called the complement. We know what we want, and still walk the whole array to look for it, again and again.
The key insight: remember what you've seen
The shopkeeper's notebook: walk down the aisle once. For each product:
- Compute what you still need:
need = 500 - price. - Glance at the notebook: have you already seen
need? If yes, you're done. - Otherwise, write this price (and its shelf number) in the notebook and keep walking.
The notebook in Java is a HashMap.
What a HashMap is
A HashMap<K, V> stores key → value pairs. Here the key is a number from the array and the value is its index.
A hash function turns a key into a bucket number, like a hostel where your room number is worked out from your roll number: nobody searches the corridor. So put, get and containsKey go straight to one bucket.
| Operation | Meaning | Average time |
|---|---|---|
map.put(k, v) |
store v under key k (replaces an old value) | O(1) |
map.get(k) |
the value for k, or null if k is missing |
O(1) |
map.containsKey(k) |
is k in the map? | O(1) |
map.getOrDefault(k, d) |
the value for k, or d if missing | O(1) |
The cost is memory: up to n entries, so O(n) extra space. (Worst case, when many keys collide in one bucket, operations can degrade, but Java's HashMap handles this well and the average is O(1).)
Dry run: nums = [3, 8, 5, 11, 1], target = 6
| i | nums[i] | need = 6 - nums[i] | in seen? | seen after |
|---|---|---|---|---|
| 0 | 3 | 3 | no | {3→0} |
| 1 | 8 | -2 | no | {3→0, 8→1} |
| 2 | 5 | 1 | no | {3→0, 8→1, 5→2} |
| 3 | 11 | -5 | no | {3→0, 8→1, 5→2, 11→3} |
| 4 | 1 | 5 | yes, at 2 | return [2, 4] |
The optimal solution: one pass
import java.util.*;
public class Main {
static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
System.out.println(Arrays.toString(twoSum(new int[]{3, 2, 4}, 6)));
System.out.println(Arrays.toString(twoSum(new int[]{3, 3}, 6)));
System.out.println(Arrays.toString(twoSum(new int[]{-3, 4, 3, 90}, 0)));
System.out.println(Arrays.toString(twoSum(new int[]{1, 2, 3}, 100)));
}
}
Output:
[0, 1]
[1, 2]
[0, 1]
[0, 2]
[-1, -1]
Duplicates ([3, 3]), negative numbers and "no answer" all work. On 1,000,000 prices with the answer at the end:
[999998, 999999] 367 ms
The same solution in C++ and Python
#include <bits/stdc++.h>
using namespace std;
vector<int> twoSum(const vector<int>& nums, int target) {
unordered_map<int, int> seen; // value -> index
for (int i = 0; i < (int)nums.size(); i++) {
int need = target - nums[i];
auto it = seen.find(need);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {-1, -1};
}
int main() {
auto a = twoSum({2, 7, 11, 15}, 9);
cout << "[" << a[0] << ", " << a[1] << "]\n"; // [0, 1]
auto b = twoSum({3, 2, 4}, 6);
cout << "[" << b[0] << ", " << b[1] << "]\n"; // [1, 2]
}
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return [-1, -1]
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum([3, 2, 4], 6)) # [1, 2]
print(two_sum([3, 3], 6)) # [0, 1]
Complexity
| Approach | Time | Extra space | Keeps original indexes? |
|---|---|---|---|
| Every pair | O(n²) | O(1) | yes |
| HashMap, one pass | O(n) average | O(n) | yes |
| Sort + two pointers | O(n log n) | O(1) to O(n) | only if you store them |
Sort + two pointers: sort, put L at the start and R at the end. If nums[L] + nums[R] is too small, move L right; too big, move R left. It returns the right values, but sorting moves elements, so you must store the original indexes. This two-pointer idea returns in 3Sum (episode 6).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
seen.put(nums[i], i) before the check |
[0, 0] for [3, 2, 4], target 6 |
finds the element it just added: 3 + 3 | check first, then put |
int j = seen.get(need); without a check |
NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null |
get returns null for a missing key, and null can't become an int |
containsKey first, or getOrDefault(need, -1) |
| two nested loops for n = 10⁵ | Time Limit Exceeded | O(n²) pairs | one pass with a HashMap |
| sort, then return indexes | wrong indexes | sorting moves the elements | keep original indexes, or use the map |
Mini project: the gift card helper
Read prices from input and print the two products that use the card exactly:
import java.util.*;
public class Main {
public static void main(String[] args) {
String[] items = {"Notebook", "Pen set", "Bottle", "Headphones", "Mug"};
int[] price = {120, 80, 350, 420, 150};
int card = 500;
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < price.length; i++) {
Integer j = seen.get(card - price[i]);
if (j != null) {
System.out.println(items[j] + " + " + items[i] + " = " + card);
return;
}
seen.put(price[i], i);
}
System.out.println("No pair uses the card exactly");
}
}
Output:
Pen set + Headphones = 500
Using Integer j (not int) lets us compare with null safely.
Practice
- Count how many pairs
(i < j)add up totargetin[1, 5, 7, -1, 5], target 6.
Solution
Keep a count of each value seen so far; for each x, add count[target - x] before recording x.
int[] a = {1, 5, 7, -1, 5};
int target = 6, pairs = 0;
Map<Integer, Integer> count = new HashMap<>();
for (int x : a) {
pairs += count.getOrDefault(target - x, 0);
count.put(x, count.getOrDefault(x, 0) + 1);
}
System.out.println(pairs); // 3: (1,5), (7,-1), (1,5)
- Return the two values instead of their indexes.
Solution
A HashSet<Integer> is enough: if set.contains(target - x) return {target - x, x}, else set.add(x). O(n) time, O(n) space.
- Solve Two Sum with sort + two pointers, returning the original indexes.
Solution
Build an array of {value, index} pairs, sort it by value, then move L and R inward. When the sum matches, return the two stored indexes. O(n log n) time.
- Is there a pair with difference exactly k?
Solution
For each x, check whether x - k or x + k is already in a HashSet, then add x. O(n).
Quick quiz
What does the HashMap solution return for twoSum(new int[]{1, 4, 4, 7}, 8)?
- [0, 3]
- [1, 2]
- [2, 1]
- [-1, -1]
Answer
[1, 2]. i = 0: need 7, not seen. i = 1: need 4, not seen, remember 4 → 1. i = 2: need 4, seen at index 1 → return [1, 2], before the loop ever reaches the 7.
Interview questions
- Why is the HashMap solution O(n)? One loop over n elements; each
containsKey,getandputis O(1) on average. - Why check before inserting? So the map only holds earlier elements, and an element can never pair with itself.
- What if the array is sorted? Use two pointers for O(n) time and O(1) space.
- What is a hash collision? Two keys landing in the same bucket. Java's HashMap chains them (and turns long chains into trees), so lookups stay fast on average.
- Can there be overflow in
target - nums[i]? With values near the int limits, yes; uselongif the constraints allow values near ±2³¹.
Glossary
| Term | Meaning |
|---|---|
| Index | The position of an element in an array, starting at 0 |
| Target | The sum we are looking for |
| Complement | The number we still need: target - x |
| Hashing | Turning a key into a bucket number with a fixed rule, for fast lookup |
| Hash function | The rule that maps a key to a bucket |
| Bucket | One slot of the hash table where keys with the same hash live |
| HashMap | Java's key → value table built on hashing |
| Key / value | What you look up by (the number) / what you store with it (its index) |
null |
"no object": what get returns for a missing key |
| NullPointerException | The crash when Java tries to use null as a real object or number |
| Two pointers | Two indexes moving through a (sorted) array toward each other |
| Average case | The expected cost over typical inputs (HashMap operations: O(1)) |
Summary
- Brute force tries every pair: O(n²), Time Limit Exceeded for big n.
- For each x we need exactly one number,
target - x, the complement. - A HashMap remembers what we've seen, with O(1) average lookups.
- Check first, then put: O(n) time, O(n) space.
Next episode: Best Time to Buy and Sell Stock, and the running minimum.