📖 9 min read
Last updated on

Two Sum — Coding Interview Walkthrough

By intervu.dev

Hero Image for Two Sum

You’re in a coding interview. The interviewer says: “Given an array of integers and a target, find the two numbers that add up to the target.” You know it’s Two Sum. You’ve solved it before. But now you need to explain your thinking out loud, justify why a hash map beats brute force, and handle follow-ups about duplicates and edge cases while someone watches. That’s a very different challenge.

This walkthrough covers how that conversation unfolds: the clarifying questions that set you apart, the brute-force-to-optimal progression interviewers want to see, and the common traps that catch even prepared candidates.

The Problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. You may assume that exactly one valid answer exists, and you cannot use the same element twice. (LeetCode #1)

Example

Input

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

Output

[0, 1, "easy"]

Explanation: Because nums[0] + nums[1] = 2 + 7 = 9, the answer is indices 0 and 1. The problem asks for indices, not the values themselves. This detail trips up more candidates than you’d expect.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Two Sum is deceptively simple, which is precisely why it reveals so much. Interviewers aren’t just checking if you know about hash maps. They’re watching how you approach an unfamiliar constraint and whether you can optimize your thinking in real time.

SkillWhat Interviewers Observe
Problem comprehensionDo you notice “return indices” vs. “return values”?
Clarification habitsDo you ask about duplicates, negative numbers, and constraints before coding?
Brute-force reasoningCan you explain a naive solution before jumping to the optimal one?
Hash map intuitionDo you recognize the space/time tradeoff?
CommunicationAre you narrating your thinking or coding in silence?
Edge case awarenessDo you consider empty arrays, single elements, or no valid pair?

Step 1 — Clarifying Questions

Before writing a single line of code, a strong candidate takes 60–90 seconds to ask clarifying questions. Here are the five most important ones for Two Sum:

  • Can the array contain negative numbers or zeros? This confirms whether constraints like “sorted, positive integers” apply. It matters less for the hash map approach, but shows you’re thinking generally.

  • Are there duplicate values in the array? If nums = [3, 3] and target = 6, the answer is [0, 1]. Knowing duplicates are possible helps you avoid incorrectly filtering them out.

  • Is there guaranteed to be exactly one solution? LeetCode guarantees this, but in a real interview you might be expected to handle no-solution or multiple-solution cases. Asking signals maturity.

  • Should I return the indices in sorted order, or in the order I find them? A subtle but valid question. It shows you read output requirements carefully.

  • What are the constraints on array size and value range? Knowing n can be up to 10,000 helps you justify why an O(n²) solution is likely too slow in production, and why O(n) matters.

Step 2 — A First (Non-Optimal) Idea

The most natural first instinct is a brute-force nested loop: for every element, check every other element to see if they sum to target.

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j, "easy"]

This works correctly, but it’s O(n²) in time complexity. For an array of 10,000 elements, that’s up to 100 million comparisons. Space complexity is O(1), which is a genuine upside worth mentioning.

ApproachTime ComplexitySpace Complexity
Brute force (nested loops)O(n²)O(1)

Always present this approach first. It shows you can build a working solution before optimizing, which is exactly what interviewers want to see. Then say: “This works, but I think we can do better. Can I walk you through an optimized approach?”

Step 3 — The Key Insight

The core insight is straightforward:

Instead of looking forward for a complement, you can remember what you’ve already seen. As you iterate through the array, for each number x, you’re really asking: “Have I already seen target - x somewhere earlier in the array?”

If yes, you’re done. If no, store x and its index for future reference.

This transforms a two-pass search into a single-pass lookup. A hash map (dictionary) gives you O(1) average-case lookup, which brings the whole algorithm down to O(n) time. The tradeoff is O(n) extra space, which is almost always worth it.

In an interview, you’d explain this like so:

“I’m going to trade space for time here. As I iterate, I’ll store each number and its index in a dictionary. For every new number, I check if its complement, target minus that number, is already in the dictionary. If it is, I’ve found my pair. This gives me O(n) time instead of O(n²).”

Array [2,7,11,15] flat cells — index 0 labeled seen (teal), index 1 showing complement=2 found — no arrows or linked nodes. ---

Step 4 — Optimal Strategy

  1. Initialize an empty dictionary called seen to store {value: index}.
  2. Iterate through nums with both index i and value num.
  3. Compute complement = target - num.
  4. Check if complement is already in seen.
  5. If yes, return [seen[complement], i]. You found the pair.
  6. If no, add num: i to seen and continue.
  7. If the loop ends with no result, return an empty list (or raise an error, depending on requirements).

The key detail: you check before inserting, so you never accidentally pair an element with itself.

Python Implementation

def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}  # Maps value -> index for numbers we've already visited

    for i, num in enumerate(nums):
        complement = target - num  # What we need to find

        if complement in seen:
            # Found the complement, return both indices
            return [seen[complement], i, "easy"]

        # No pair yet, store this number for future lookups
        seen[num] = i

    return []  # No valid pair found (shouldn't happen per problem constraints)

Why this is interview-friendly:

  • Using enumerate instead of range(len(...)) is more Pythonic and readable.
  • The variable name complement clearly communicates intent.
  • The comment explaining why you check before inserting shows self-awareness about potential edge cases.

Time Complexity

OperationComplexity
Iterating through the arrayO(n)
Each dictionary lookup/insertO(1) average
Overall timeO(n)
Space (hash map)O(n)

Time: We iterate through the array once. Each dictionary lookup and insertion is O(1) on average, giving us O(n) total.

Space: In the worst case (no valid pair until the last two elements), we store every element in the dictionary — O(n) space.

Compare this to brute force: O(n²) time, O(1) space. The hash map solution is strictly better when n is large and memory isn’t the bottleneck, which is almost always the case.

Common Interview Mistakes

  • Returning values instead of indices. Re-read the problem. It asks for [0, 1], not [2, 7]. This mistake happens when candidates scan the problem too quickly.

  • Inserting before checking. If you do seen[num] = i before checking complement in seen, you risk pairing nums[i] with itself when num * 2 == target.

  • Using a nested loop without explaining why you’d move away from it. The brute force isn’t wrong; it’s just not optimal. Failing to mention this tradeoff signals you don’t know there’s a better way.

  • Not mentioning space complexity. The hash map solution uses O(n) extra memory. Interviewers often ask “what’s the tradeoff?” so have the answer ready.

  • Coding in silence. Two Sum is fast to code, but if you say nothing while typing, you give the interviewer nothing to evaluate. Narrate your thinking continuously.

  • Assuming the array is sorted. Some candidates jump to a two-pointer approach, which only works on sorted arrays. Two Sum doesn’t guarantee sorted input, so always clarify before assuming.

  • Forgetting the edge case where no valid pair exists. The LeetCode problem guarantees a solution, but mentioning “and if there’s no valid pair, I’d return an empty list” demonstrates defensive programming instincts.

What a Strong Candidate Sounds Like

“Before I start coding, let me make sure I understand the constraints. The array isn’t necessarily sorted, and there’s guaranteed to be exactly one valid answer — so I don’t need to handle no-solution cases. I also want to confirm we can’t use the same element twice.

My first idea is a brute-force double loop — O(n²), which is correct but slow. I think I can do better. As I iterate, for each number I can ask ‘have I already seen its complement?’ and store previous values in a dictionary. That gives me a single-pass O(n) solution with O(n) space. The tradeoff is acceptable here. Let me code that up.”

This response covers problem restatement, clarifying questions, naive approach, optimization reasoning, and complexity analysis, all before touching the keyboard.

Example Interview Dialogue

Interviewer: Let’s start with Two Sum. Can you walk me through your thinking?

Candidate: Sure. So I’m given an array and a target, and I need to find two indices whose values add up to the target. Before I code, can I ask: is the array guaranteed to have a solution, and can values be negative?

Interviewer: Yes, exactly one solution exists. Values can be anything.

Candidate: Got it. My first instinct is a nested loop to check every pair. That’s O(n²), which works but isn’t great for large inputs. I think I can use a hash map to get this down to O(n). As I iterate, I store each number and its index, and for every new number I check if its complement, target minus num, is already stored.

Interviewer: What happens if the same number appears twice and its double equals the target? Like [3, 3] with target 6?

Candidate: Good catch. That’s exactly why I check the dictionary before inserting the current number. When I reach the second 3, its complement 3 is already stored from the first pass, so I return [0, 1] correctly without pairing an element with itself.

Interviewer: Nice. What’s the space complexity?

Candidate: O(n) in the worst case. If no pair exists until the very end, I’ve stored every element. The time is also O(n) since each lookup is O(1) average.

Once you’ve mastered Two Sum, these problems build on the same hash map and complement-lookup patterns:

  • Two Sum II, Input Array Is Sorted (LeetCode 167). Same goal with sorted input, introducing the two-pointer technique as an alternative.
  • 3Sum (LeetCode 15). Extends Two Sum to three elements, combining sorting with the complement approach.
  • 4Sum (LeetCode 18). Pushes the pattern further and tests generalization and pruning.
  • Subarray Sum Equals K (LeetCode 560). Uses prefix sums + hash maps, directly extending the “store what you’ve seen” insight.
  • Two Sum III, Data Structure Design (LeetCode 170). What if the array is a stream? Tests API design with Two Sum as the core.

From the Intervu walkthrough collection:

  • 3Sum — Extends Two Sum to three elements with sorting + two pointers.
  • Contains Duplicate — Hash set for O(n) duplicate detection.
  • Valid Anagram — Character frequency counting with hash maps.

Practice This in a Mock Interview

Reading a walkthrough helps you internalize the approach, but reading and performing are completely different skills. In a real interview, you’re typing while talking, managing nerves, and responding to follow-up questions in real time. The only way to get comfortable is to practice under realistic conditions.

Understanding Two Sum is step one. Executing it clearly and confidently when someone is watching takes reps.

Start a mock interview for Two Sum on Intervu and practice with a realistic AI interviewer that gives instant feedback on your approach.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →