DSA Explained
#1

Two Sum

Easy
LeetCode

Given a list of numbers nums and an integer target, find the two numbers that add up to the target, and return their positions (indices).

💡 In plain English

You have a list like [2, 7, 11, 15] and target 9. Since 2 + 7 = 9, their positions are 0 and 1, so the answer is [0, 1]. Each problem has exactly one answer, and you cannot use the same number twice.

Reference: LeetCode #1 • Two Sum

Approach
Execution Timeline (Optimal (Hash Map))Click any step to inspect state & code

Algorithm Visualization

Optimal Approach (One-Pass Hash Map)
Step 3 / 5
3

Look at 11 (index 1)

IN PROGRESS

We look at 11. To reach target 9, we need partner -2 (9 - 11 = -2). Have we seen -2 before? No. So we save { 11: index 1 } and move to the next number.

Array (nums)length = 4
2
[0]
11
[1]↓ i
7
[2]
15
[3]
Target
9
nums[i] + complement
Hash Map Table2 entries
Key: 2→Idx: 0
Key: 11→Idx: 1
Current VariablesMemory
nums[i]11 (i=1)
Complement (9 - nums[i])-2
Partner -2 not seen yet. Wrote down 11 -> index 1.
1
function twoSum(nums, target) {
2
const map = new Map();
3
for (let i = 0; i < nums.length; i++) {
4
const complement = target - nums[i];
5
if (map.has(complement)) {
6
return [map.get(complement), i];
7
}
8
map.set(nums[i], i);
9
}
10
return [];
11
}
Optimal (Hash Map) • Synchronized Line TraceLine 8 of 11
→ Executing Statement:-2 not in map. Save key 11 with index 1: map.set(nums[i], i);

Why is the Hash Map Solution Best?

How to think through the problem and discover the fast solution yourself step by step.

Step-by-Step Logic
01. Simple Idea

Brute Force

Test every possible pair one by one using two nested loops.

Work: Checks every pair
02. The Flaw

Why is it slow?

For 10,000 numbers, checking all pairs takes ~50 million checks. It is too slow!

Speed: Slow O(n²) time
03. The Clue

What partner do we need?

For any number x, we know the exact partner we need: target - x.

Goal: "Have we seen this partner?"
04. The Solution

Use a Notebook

Write each number down in a hash map notebook as you pass it. Looking inside takes 1 instant step!

Lookup: Instant O(1) checks
05. Optimal

One Single Pass

Walk through the list once. Check if the partner is in your notebook. If yes, you are done!

Result: Fast O(n) time
Active Selection Details

Optimal Approach (One-Pass Hash Map)

Time: O(n) — FastSpace: O(n) — Uses little memory
Time Complexity: O(n) — Fast
Best:O(1)
Average:O(n)
Worst:O(n)

We walk through the list of numbers only once. Looking up or adding an item in a hash map happens in 1 quick step.

Space Complexity: O(n) — Uses little memory
Auxiliary Memory: O(n)

In the worst case, we save up to n numbers in our notebook until we find the match.

Example Test Cases

Simple examples
Example 1
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Because 2 + 7 = 9, we return their positions: [0, 1].
Example 2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Because 2 + 4 = 6, we return their positions: [1, 2].
Example 3 (Same Values)
Input: nums = [3, 3], target = 6
Output: [0, 1]
Both numbers are 3, but they are at two different spots (index 0 and index 1).

Rules & Limits

Constraints
  • At least 2 numbers

    The list will always have 2 or more numbers, up to 10,000 numbers (2 ≤ nums.length ≤ 10⁴).

  • Numbers can be negative

    Numbers can be positive, negative, or zero (-10⁹ ≤ nums[i], target ≤ 10⁹).

  • Exactly one solution

    You are guaranteed that exactly one valid pair exists.

  • Cannot use the same number twice

    You cannot use the element at the same index twice.

Important Things to Remember

Key Lessons
1. The Partner Number Trick

Instead of adding every pair, calculate what number you need: needed = target - current. Then check if you have already seen that partner!

2. Use Memory to Go Fast

Two loops take O(n²) time (slow). Storing seen numbers in a quick-lookup hash map takes a tiny bit of extra memory, but solves the problem in just 1 pass (fast O(n)).

3. Check Before Saving

Check your notebook before saving the current number. This guarantees you will never accidentally pair a number with itself!

Related Problems & Pattern Practice: Explore All 12 Patterns →
#2 Add Two Numbers (Medium) #3 Longest Substring Without Repeating Characters (Medium) #167 Two Sum II - Input Array Is Sorted (Medium) #15 3Sum (Medium) #560 Subarray Sum Equals K (Medium)