What are the common mistakes?

- Storing the number before checking for its partner, which lets an element pair with itself (e.g. target 6 with a single 3). - Sorting first to use two pointers, which loses the original indices the answer needs. - Returning the numbers instead of their positions.

DSA patterns

Two Sum

easyArrays and hashing Must-do

You get a list of integers and a target number. Return the positions of the two numbers that add up to the target. Exactly one valid pair exists, and you can't use the same element twice.

Examples

Example 1

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

Output: [0, 1]

Explanation: nums[0] + nums[1] = 2 + 7 = 9.

Approach

Optimal

Checking every pair works but is slow: for 10,000 numbers that's about 50 million comparisons. Flip the question instead. For each number, you already know which partner it needs: target minus the number. If you remember every number you've seen in a dictionary, you can check for that partner in constant time as you go.

Create an empty dictionary that maps a number to its index.
Walk through the list once. For each number, compute its partner: target - number.
If the partner is already in the dictionary, return the partner's index and the current index.
Otherwise, store the current number and its index, then move on.

ComplexityTime O(n)Space O(n)

Python

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # number -> index where we saw it
    for i, num in enumerate(nums):
        partner = target - num
        if partner in seen:
            return [seen[partner], i]
        seen[num] = i
    return []  # the problem guarantees a pair, so this is never reached

Frequently asked questions

This "remember what you've seen, look up what you need" trick is the core of most practical infra coding rounds. Matching request and response log lines by request ID, pairing a deploy event with its rollback, or finding two cost items that add up to a budget alert all use the same one-pass dictionary.

Storing the number before checking for its partner, which lets an element pair with itself (e.g. target 6 with a single 3).
Sorting first to use two pointers, which loses the original indices the answer needs.
Returning the numbers instead of their positions.