Skip to content

Volume ITechnology

4.4.3 — Two Sum ​

LeetCode 1 · Easy · ★ Blind 75

The problem ​

You are given a list of numbers called nums and one number called target. Find the two positions in the list whose numbers add up to target. Return those two positions.

nums = [2, 7, 11, 15], target = 9   →  [0, 1]    because 2 + 7 = 9
nums = [3, 2, 4],      target = 6   →  [1, 2]    because 2 + 4 = 6
nums = [3, 3],         target = 6   →  [0, 1]    because 3 + 3 = 6

The list has between 2 and 10,000 numbers. The problem promises that exactly one answer exists. You may not use the same position twice.

Notice the third example. The two values are both 3, and that is allowed. Only the two positions must be different.

What the problem is really asking ​

Pick any number in the list, say 7, with a target of 9. The only number that can pair with 7 is 9 - 7 = 2. Nothing else works.

So for each number, its partner is already decided. We write it as need = target - number. The problem is really asking: "for some number, does its partner appear somewhere else in the list, and where?"

That turns a search for a pair into a search for one known value.

The brute force, and where it wastes work ​

Try every pair of positions.

python
def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):          # every position after i
            if nums[i] + nums[j] == target:
                return [i, j]

This makes about \frac{n^2}{2} checks. For 10,000 numbers that is 50 million checks. It passes, but slowly, and the interviewer will ask for better.

The waste in one sentence: for each i, the inner loop is just searching the list for one known value, target - nums[i], and it repeats that search from scratch every time.

The idea ​

Remember every number you have walked past, together with its position. Then, for the current number, compute the partner it needs and ask the memory, "have I already seen the partner, and where?"

The memory is a hash map, also called a dictionary. A hash map stores pairs of key → value and finds a key in about constant time. Here the key is a number from the list, and the value is its position.

Why store number → position, and not the other way round? Because we search by number ("is 2 in here?") and we must return a position. The thing you search by is the key. The thing you want back is the value.

The solution ​

python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}                              # (1)
        for i, n in enumerate(nums):           # (2)
            need = target - n                  # (3)
            if need in seen:                   # (4)
                return [seen[need], i]         # (5)
            seen[n] = i                        # (6)
        return []                              # (7)
ts
function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();      // (1)
  for (let i = 0; i < nums.length; i++) {      // (2)
    const need = target - nums[i];             // (3)
    if (seen.has(need)) {                      // (4)
      return [seen.get(need)!, i];             // (5)
    }
    seen.set(nums[i], i);                      // (6)
  }
  return [];                                   // (7)
}

Line by line ​

(1) seen = {}. An empty map. It will hold "number → the position where I saw it". It starts empty because we have not walked past anything yet.

(2) for i, n in enumerate(nums). enumerate hands us two things on each turn: the position i and the number n at that position. We need both, because we look up by number and return positions.

(3) need = target - n. The partner that would complete the sum. If n is 7 and target is 9, then need is 2. This is the line that turns "search for a pair" into "look up one value".

(4) if need in seen. Have we already walked past the partner? Looking a key up in a map is constant time on average, so this replaces the whole inner loop of the brute force.

(5) return [seen[need], i]. Found it. seen[need] is the earlier position where the partner sits, and i is where we are now. The earlier position comes first, which is the order the examples use. In TypeScript, the ! after get(need) tells the compiler "I know this is not missing", which is safe because line (4) just checked.

(6) seen[n] = i. The partner is not here yet. So we remember the current number and its position, in case a later number needs it as its partner.

(7) return []. The problem promises an answer exists, so this line never runs on valid input. It is there so the function always returns a list, which TypeScript requires.

Why one pass is enough ​

You might wonder: when we are at position i, the partner might be later in the list, and we have not seen it yet. Do we miss it?

No. Every answer is a pair of positions, one earlier and one later. When the loop reaches the earlier one, its partner is not in the map yet, so we store it and move on. When the loop later reaches the second one, its partner (the earlier one) is already in the map, so line (4) finds it. Every pair gets caught at its second position. You never need to look ahead.

Why line (4) comes before line (6) ​

Take nums = [3, 3] and target = 6, but imagine we stored first and checked second.

  1. At position 0, we store 3 → 0.
  2. Then we ask, "is need = 3 in the map?" Yes, at position 0.
  3. We return [0, 0].

That uses the same position twice, which is not allowed. The same thing breaks [3, 2, 4] with target 6: position 0 would pair 3 with itself.

So we check first, then store. Then at position 0 the map is still empty, the check fails, and we store 3 → 0. At position 1, the check finds the other 3 at position 0, and we return [0, 1]. This is the same rule you met in 4.4.1: an element must never match itself.

Trace ​

Take nums = [2, 7, 11, 15] and target = 9.

inneed = 9 − nIs need in seen?Actionseen after
027nostore 2 → 0
172yes, at 0return [0, 1]—

Now nums = [3, 2, 4] and target = 6.

inneed = 6 − nIs need in seen?Actionseen after
033no (map empty)store 3 → 0
124nostore 2 → 1
242yes, at 1return [1, 2]—

Notice the first row. The 3 needs another 3, but the map is empty, so it does not match itself. Check before store did its job.

Complexity, derived ​

Time. The loop runs at most n times. Each turn does one subtraction, one map lookup and at most one map insert. Each of those takes constant time on average. So the total is n turns times a constant, which is O(n).

Space. In the worst case the answer is the last two positions, and we store almost every number before finding it. So the map can hold up to n - 1 entries, which is O(n).

Edge cases ​

  • Two equal values, such as [3, 3]. Works because of check-before-store, as shown above.
  • Negative numbers, such as nums = [-3, 4, 3, 90], target = 0. The partner of −3 is 0 - (-3) = 3. The subtraction handles signs by itself.
  • Zero, such as [0, 4, 3, 0] with target = 0. The partner of 0 is 0. The two zeros are at different positions, so it works.
  • A value that repeats but is not part of the answer, such as [3, 5, 3]. The second 3 overwrites the first in the map. That is harmless. We only ever need one position for each value, and the earlier 3 already had its chance to be found.

Why not sort and use two pointers? ​

If the list were sorted, you could put one pointer at each end and move them inward, using no extra memory. That is 4.5.2 Two Sum II.

You cannot do it here, because sorting moves the numbers to new positions, and positions are exactly what the problem asks for. To keep them, you would have to sort (value, original position) pairs. That needs O(n) extra memory anyway, and the sort costs O(n \log n) time. So you would pay more time and save no memory.

The rule: unsorted input and the answer is positions → hash map. Sorted input → two pointers.

Variations you will meet ​

  • Two Sum II. The list is sorted, so two pointers work in O(1) extra memory. 4.5.2.
  • 3Sum. Find three numbers that add to zero. Sort, fix the first number, then run Two Sum II on the rest. 4.5.3.
  • Subarray Sum Equals K. Count the stretches of the list that add to k. You keep a running total as you walk, and store running totals in the map instead of single values. Then, for each running total, you look up total − k. It is the same "compute what I need, then look it up" move with a different thing in the map. This is the most useful generalisation of Two Sum.

The general lesson: when you need two things that fit a rule, fix one, work out the other from the rule, and look it up.

What the interviewer will push on ​

"Why store number → position and not position → number?" They are checking that you designed the map. You search by number, so the number is the key.

"What happens with [3, 3]?" They are checking check-before-store. If you store first, you return [0, 0].

"Can you do it in O(1) extra memory?" Only by sorting, and sorting loses the positions. Explain why that costs more than it saves.

"What if there can be many answers, and you must return all of them?" Then you cannot return on the first match. Store each value's list of positions, and be careful not to count a pair twice.

One thing to volunteer: explain why one pass is enough. Every pair is caught when the loop reaches its second position. That shows you understand the algorithm rather than remember it.

Next: 4.4.4 Group Anagrams. Now the interesting part is not the map but the key you put into it.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet