SyntaxPilot
Courses/DSA and Coding Problems/Lesson 2
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 2 of 90

Two Sum (hashing)

queued

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 an int.
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)/2 pairs: 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:

  1. Compute what you still need: need = 500 - price.
  2. Glance at the notebook: have you already seen need? If yes, you're done.
  3. 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

  1. Count how many pairs (i < j) add up to target in [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)
  1. 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.

  1. 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.

  1. 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

  1. Why is the HashMap solution O(n)? One loop over n elements; each containsKey, get and put is O(1) on average.
  2. Why check before inserting? So the map only holds earlier elements, and an element can never pair with itself.
  3. What if the array is sorted? Use two pointers for O(n) time and O(1) space.
  4. 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.
  5. Can there be overflow in target - nums[i]? With values near the int limits, yes; use long if 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.