Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Easy

Two Sum

Two Sum explained: the one-pass hash map trick that turns an O(n²) pair search into O(n), with tested Python code, common mistakes and a live visual.

Also searched as: two sum hash map solution · find two numbers that add up to target · pair with given sum

#️⃣

Try it live Free

Hash Tables

Insert keys into the hash table and watch each one land in its bucket in O(1). That constant-time lookup is exactly what lets Two Sum ask "have I seen target minus x?" at every step.

Also useful: Two Pointers

Open the playground →

The problem

You are given a list of integers nums and an integer target. Return the indices of the two different positions whose values add up to target. You may assume exactly one such pair exists.

Inputnums = [2, 7, 11, 15], target = 9
Output[0, 1]

2 + 7 = 9.

Inputnums = [3, 3], target = 6
Output[0, 1]

The same value can appear twice, but you cannot use one index twice.

The key insight

For every number x, the partner you need is fixed: target - x. So instead of searching for a pair, ask a cheaper question at each step: have I already seen the partner? A hash map from value to index answers that in O(1), so one left-to-right pass is enough.

Brute force first: Checking every pair with two nested loops is correct but takes O(n²) time.

Step-by-step approach

  1. Create an empty dictionary seen mapping value to index.
  2. Walk the list with i and value x.
  3. Compute need = target - x. If need is in seen, return [seen[need], i].
  4. Otherwise store seen[x] = i and continue.
  5. Checking before inserting guarantees you never pair an index with itself.

Python solution

PYTHON 3tested
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 []                      # no pair (problem says this will not happen)

Complexity

TimeO(n)
SpaceO(n)

Each element is looked up and inserted once, and dictionary operations are O(1) on average. In the worst case the map holds every element.

Common mistakes

Frequently asked questions

What is the time and space complexity of Two Sum?

The hash map solution is O(n) time and O(n) extra space. The brute-force double loop is O(n²) time and O(1) space.

Can Two Sum be solved without extra space?

If you only need the values, sort the array and use two pointers in O(n log n) time. If you need the original indices, sort pairs of (value, index), which still uses O(n) space.

How do duplicates like [3, 3] with target 6 work?

When you reach the second 3, the first 3 is already in the map, so you return both indices. Because you check before inserting, a single 3 never pairs with itself.

What if there can be several valid pairs?

The one-pass method returns the first pair it completes. To return all pairs, keep a count map and collect matches instead of returning early.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.