How to Solve Two Sum

Use a one-pass hash map keyed by value and storing index. For each number, compute the complement target - nums[i] and check whether that complement was seen earlier; if yes, return those two indices immediately. This avoids the nested-loop failure mode where you rescan earlier elements for every index.

Problem Statement

You are given an integer array nums and an integer target, and you need to return the two indices whose values add up exactly to target. The output is based on positions, not the numbers themselves, so the key task is locating where the matching pair appears in the array rather than just identifying the pair's values.

This input is guaranteed to contain exactly one valid answer, and you cannot use the same element twice. That restriction matters when the target is twice a number, because you still need two different indices. The main challenge is finding the match without doing a full quadratic scan across all possible pairs.

Examples

Example 1

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1]

When you read 7, the missing value is 2. Because 2 has already been stored in the hash map at index 0, you can return [0, 1].

Example 2

Input: nums = [3, 2, 4], target = 6

Output: [1, 2]

The pair is 2 and 4. The hash map lets you recognize the complement of 4 as soon as you reach index 2.

Constraints

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Exactly one valid answer exists, and you may not reuse the same element twice.

Solution Approach

One-pass complement lookup

The cleanest solution walks through nums once while maintaining a hash map from value to index. At each position i, compute the missing value target - nums[i]. If that missing value is already in the map, you have found the earlier index and can return [storedIndex, i] immediately. Otherwise, store the current value with its index and continue. This order matters: checking before inserting prevents pairing an element with itself when target equals 2 * nums[i] and only one copy has appeared so far.

Why the hash map beats brute force here

A brute-force solution tries every pair of indices and checks whether their values sum to target, which works but wastes time revisiting combinations that the complement idea avoids. In Two Sum, the only fact you need at index i is whether the exact complement has been seen earlier. The hash map turns that question into constant-time lookup. The trade-off is extra memory, but that memory directly eliminates repeated scans and is the reason the solution scales cleanly to the problem's input size.

Handling duplicates and index correctness

Two Sum often trips people up when duplicate values appear, such as needing two copies of the same number to reach the target. Storing value-to-index pairs still works because you only need one earlier occurrence to form the valid answer, and the problem guarantees exactly one solution. The important detail is returning indices, not sorted values or the numbers themselves. Since the map stores indices from earlier positions, the returned pair naturally uses two distinct elements and satisfies the no-reuse rule.

Complexity Analysis

The provided time complexity is O(n) because each element is processed once, with one complement lookup and at most one insert into the hash map. The provided space complexity is O(n) because, in the worst case, the map stores nearly every value before the valid pair is found. That extra memory is exactly what removes the quadratic pair scan.

What Interviewers Usually Probe

• Do you recognize that Two Sum only needs a complement existence check, not comparison against every later element?
• Can you explain why checking the hash map before inserting the current value avoids reusing the same index?
• Will you justify the memory-for-speed trade-off that changes the solution from O(n^2) to O(n)?

Common Pitfalls or Variants

Common pitfalls

• Inserting the current value before checking its complement can incorrectly pair an element with itself when the target is twice that value.
• Returning the two numbers instead of their indices misses the actual output requirement of Two Sum.
• Using a nested loop after already computing complements defeats the point of the hash map and turns this easy problem back into O(n^2).

Follow-up variants

• Return the actual values instead of indices while still using the complement lookup pattern.
• Solve Two Sum II where the array is sorted and the expected follow-up uses two pointers instead of a hash map.
• Count how many distinct index pairs sum to the target, which changes duplicate handling and prevents early return after one match.

How GhostInterview Helps

• You can screenshot or capture the Two Sum prompt, examples, and constraints so the solver reads the exact target, array, and required index output.
• GhostInterview gives the answer path from brute force to one-pass hash map, then explains why the complexity is O(n) time and O(n) space.
• It supports screen-share workflows and captured layers, so the solver can read the problem statement, code editor, or example trace from whichever layer you expose.

Topic Pages

• Array
• Hash Map

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

Why is a hash map the right pattern for Two Sum?

Because each index only needs one specific missing value: target - nums[i]. A hash map answers whether that complement already appeared, which turns repeated pair scanning into direct lookup and makes the problem linear.

Why do we check the complement before storing the current number?

That order prevents using the same element twice. If you store first, a value could match itself immediately when the target is double that number, even though only one index has been seen.

Does Two Sum still work when duplicate numbers appear?

Yes. Duplicates are fine because the map tracks indices, not just values conceptually. When the second needed copy appears, it can match the earlier stored index and return two distinct positions.

Why not sort the array first to make searching easier?

Sorting changes index positions, which breaks the original-index requirement unless you carry extra bookkeeping. For this problem, the one-pass hash map is simpler and directly preserves the correct indices.

What is the main failure mode in the Two Sum complement lookup pattern?

The usual mistake is mishandling self-pairing or returning values instead of indices. Another common issue is overcomplicating the problem with sorting or nested loops when a direct complement check already solves it.