Two Sum — The Complete Interview Walkthrough (Brute Force, HashMap, and the Conversation an Interviewer Wants to Hear)

If you’re an Android developer preparing for interviews at a bigger company, the first DSA round usually starts with one specific problem. Not LinkedLists. Not trees. Two Sum. It’s the warm-up question every interviewer reaches for — not because it’s hard, but because how you approach it tells them everything: do you jump to the optimal answer and skip the reasoning, or do you walk through brute force, talk about complexity, and then optimise? This post is the full walkthrough — the way an interviewer wants to hear it, not the way a one-liner Kotlin solution reads.

The Problem

You’re given an array of integers nums and an integer target. Return the indices of the two numbers that add up to target.

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

Output: [0, 1]

Why?
Index : 0   1   2   3
Value : 2   7  11  15

nums[0] + nums[1] = 2 + 7 = 9 ✅

So the answer is the pair of INDICES: [0, 1]
NOT the values themselves.

The first trap candidates fall into: returning the values [2, 7] instead of the indices [0, 1]. Read the question twice before you start writing code. Interviewers do notice.

Step 1 — Always Start with Brute Force

I cannot stress this enough. The interviewer is not impressed if you blurt out “HashMap, O(n), done.” They’re evaluating how you think, not whether you’ve memorised LeetCode. Your opening line should sound like:

“Let me start with a brute force approach, talk through its complexity, and then see if we can do better.”

That one sentence buys you trust. Now let’s actually solve it.

The brute force idea: check every possible pair. For each element, walk the rest of the array and see if the two add up to the target.

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

Pick i = 0 (value 2)
   Check j = 1: 2 + 7  = 9 ✅  → return [0, 1]

Done in one pair. But in the worst case, we'd check every pair.

Let’s also trace a case where the first element doesn’t pair with anything:

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

i = 0 (value 3)
   j = 1: 3 + 2 = 5 ❌
   j = 2: 3 + 4 = 7 ❌
   (3 has no partner; move on)

i = 1 (value 2)
   j = 2: 2 + 4 = 6 ✅  → return [1, 2]

The brute force code

fun twoSum(nums: IntArray, target: Int): IntArray {
    for (i in nums.indices) {
        // nums.indices is a PROPERTY on IntArray — the range 0..lastIndex
        for (j in i + 1 until nums.size) {
            // j starts at i+1 so we never pair an element with itself
            // and never re-check pairs we've already seen
            if (nums[i] + nums[j] == target) {
                return intArrayOf(i, j)
                // intArrayOf() is a TOP-LEVEL FUNCTION — builds an IntArray
            }
        }
    }
    return intArrayOf()   // problem guarantees a solution, but compiler is happy
}

Complexity of brute force

Time   : O(n²)
            Outer loop runs n times.
            Inner loop runs up to n times.
            Total comparisons ≈ n × n / 2

Space  : O(1)
            We only use two index variables.
            No extra data structure.

Step 2 — The Interviewer Asks “Can You Do Better?”

This question is coming. They’re not asking because brute force is wrong — they’re asking because they want to see if you can spot the inefficiency.

Your answer:

“Yes. The slow part of brute force is the inner loop — for every element we’re scanning the rest of the array looking for its partner. That’s O(n) per element. If we could look up a number in O(1) time, the whole algorithm becomes O(n). A HashMap gives us exactly that.”

Now you’ve earned the right to introduce the optimal solution.

Step 3 — The HashMap Insight

Here’s the key shift in thinking. Instead of asking “is there a pair that sums to target?”, ask “for the current number, what’s its missing partner — and have I seen that partner before?”

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

At value 2:  partner I need = 9 - 2 = 7
At value 7:  partner I need = 9 - 7 = 2
At value 11: partner I need = 9 - 11 = -2
At value 15: partner I need = 9 - 15 = -6

So as we walk the array, we ask: “has the partner I need already been seen?” If yes, we’re done. If no, we remember the current number so a future element can find us as its partner.

Full trace — nums = [2, 7, 11, 15], target = 9

map = {}     // empty HashMap to start

──────────────────────────────────────────────
i = 0, value = 2
   partner needed = 9 - 2 = 7
   map.containsKey(7)? → No
   Store current: map[2] = 0
   map = { 2 → 0 }

──────────────────────────────────────────────
i = 1, value = 7
   partner needed = 9 - 7 = 2
   map.containsKey(2)? → Yes!  map[2] = 0
   Return [0, 1]  ✅  Done.

Another trace — nums = [3, 2, 4], target = 6

map = {}

──────────────────────────────────────────────
i = 0, value = 3
   partner needed = 6 - 3 = 3
   map.containsKey(3)? → No
   Store: map[3] = 0
   map = { 3 → 0 }

──────────────────────────────────────────────
i = 1, value = 2
   partner needed = 6 - 2 = 4
   map.containsKey(4)? → No
   Store: map[2] = 1
   map = { 3 → 0, 2 → 1 }

──────────────────────────────────────────────
i = 2, value = 4
   partner needed = 6 - 4 = 2
   map.containsKey(2)? → Yes!  map[2] = 1
   Return [1, 2]  ✅

The HashMap code

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    // mutableMapOf() is a TOP-LEVEL FUNCTION — builds a LinkedHashMap
    // Key   = a number from the array
    // Value = the index where we saw it

    for (i in nums.indices) {
        val complement = target - nums[i]
        // "complement" = the partner we're hoping has been seen before

        if (map.containsKey(complement)) {
            return intArrayOf(map[complement]!!, i)
            // !! is safe here because containsKey() already proved it's present
            // Order matters: partner's index first (smaller), current index second
        }

        map[nums[i]] = i
        // Only add current number AFTER the check — explained below
    }
    return intArrayOf()
}

The Subtle Bug — Why Check BEFORE Inserting?

This is the question interviewers love. The order matters. If you insert first and check later, you can pair an element with itself.

nums   = [3, 3]
target = 6

❌ WRONG order — insert first, then check:

i = 0, value = 3
   map = {}
   Store first: map[3] = 0
   complement = 6 - 3 = 3
   map.containsKey(3)? → Yes  (the one WE JUST stored!)
   Return [0, 0]  — BUG! Same index used twice.

✅ CORRECT order — check first, then insert:

i = 0, value = 3
   complement = 6 - 3 = 3
   map.containsKey(3)? → No (map is empty)
   Store: map[3] = 0

i = 1, value = 3
   complement = 6 - 3 = 3
   map.containsKey(3)? → Yes (index 0)
   Return [0, 1]  ✅

Memorise this and say it out loud during the interview. It signals you’ve actually thought about edge cases, not just memorised the happy path.

Complexity of the HashMap Approach

Time   : O(n)
            Single pass through the array.
            Each HashMap lookup and insert is O(1) on average.

Space  : O(n)
            In the worst case (no pair found until the last element),
            the map ends up holding n-1 entries.

Trade-off summary you should be able to say out loud:

Brute force : O(n²) time, O(1) space   — slow, no memory cost
HashMap     : O(n)  time, O(n) space   — fast, uses extra memory

We're trading space for time. In an interview, this is almost
always the right trade-off — modern systems have more memory
than they have CPU cycles.

Edge Cases to Mention

Strong candidates don’t just write code — they think about what could go wrong. Bring these up before the interviewer does:

1. Duplicates: nums = [3, 3], target = 6
   → Works correctly because we check before inserting.

2. Negative numbers: nums = [-1, -2, -3, -4, -5], target = -8
   → Works — the math is the same.
   → (-3) + (-5) = -8  → returns [2, 4]

3. Zero in array: nums = [0, 4, 3, 0], target = 0
   → Works — complement of 0 is 0, the two 0s pair up.
   → Returns [0, 3]

4. Target equals one of the values: nums = [1, 5, 7], target = 5
   → Only matches if another number completes the pair.
   → 5 alone isn't a valid answer.

5. No solution exists:
   → Problem usually guarantees a solution, but in production code
       you'd return an Optional or null instead of an empty array.

The Conversation an Interviewer Wants to Hear

Here’s the script that wins this round. Don’t memorise it, but internalise the rhythm.

You: "Just to confirm — we're returning the INDICES, not the values,
      and the problem guarantees exactly one valid pair?"
INT: "Yes."

You: "Okay. Let me start with brute force so we have a baseline."
     [write brute force]
     "That's O(n²) time, O(1) space."

INT: "Can you do better?"

You: "Yes. The inner loop is doing a linear search for a number we
      already know we need. If I store numbers in a HashMap as I go,
      I can look up the partner in O(1)."
     [write HashMap solution]
     "That's O(n) time, O(n) space — we trade space for speed."

INT: "Why do you check the map before inserting?"

You: "To avoid pairing an element with itself. If I inserted first,
      a number like [3, 3] with target 6 would match itself at index 0
      and return [0, 0]."

INT: "What if the array has duplicates?"

You: "Still works — the check-then-insert order means the second
      occurrence finds the first one as its partner."

INT: "And the worst case of HashMap?"

You: "Average O(1) lookup, but worst case O(n) if every key hashes
      to the same bucket. For interview purposes we assume the
      average case, which is what most analyses use."

That entire exchange takes about 8 minutes. You demonstrate problem reading, baseline thinking, optimisation reasoning, edge case awareness, and complexity literacy. That’s a hire signal.

Common Follow-Up Questions

Q1. Why HashMap and not sorting?

Sorting destroys the original index order. The question asks for indices, so once you sort, you’ve lost the answer. If the question had asked for the values, sorting plus two pointers would actually be a great approach — O(n log n) time, O(1) space.

Q2. Could we use a Set instead of a Map?

A Set would tell us whether the partner exists, but not where it was. Since we need indices, we need the value-to-index mapping that only a Map provides.

Q3. What if there could be multiple valid pairs?

The problem statement here says “exactly one solution.” If multiple pairs were allowed, we’d collect them in a list and return all matches — same algorithm, just don’t return early on the first hit.

Q4. What if the array is very large — like a billion elements?

O(n) is still fine for time, but O(n) space might not fit in memory. At that scale you’d either stream through the data in chunks (which doesn’t help for Two Sum — we need random access to the partner) or use an external data structure like a disk-backed map. In a real interview, this is the “system design tangent” signal — pivot only if they push you there.

Q5. What’s the worst-case HashMap complexity?

Average is O(1) for both get and put. Worst case is O(n) per operation if all keys collide into the same bucket, making the whole algorithm O(n²) in the worst case. Java’s HashMap mitigates this by converting long collision chains to balanced trees, bringing the worst case down to O(log n) per operation. Kotlin’s mutableMapOf() uses Java’s LinkedHashMap, so the same mitigation applies.

Quick Reference

BRUTE FORCE
───────────
- Idea       : Check every pair (i, j)
- Time       : O(n²)
- Space      : O(1)
- When       : Tiny arrays, or as the "first attempt" in interviews

HASHMAP (OPTIMAL)
─────────────────
- Idea       : For each element, look up its complement in O(1)
- Time       : O(n) average, O(n²) worst case (hash collisions)
- Space      : O(n)
- Trick      : ALWAYS check before inserting (prevents self-pairing)
- When       : The expected answer in 99% of interviews

ANSWER ORDER IN AN INTERVIEW
────────────────────────────
1. Clarify the problem (indices vs values, unique solution)
2. Brute force + its complexity
3. Explain the bottleneck
4. HashMap solution + its complexity
5. Edge cases (duplicates, negatives, zeros)
6. Be ready to defend "check before insert"

Wrap-Up

Two Sum looks easy because the optimal solution is six lines of code. The thing that catches people out isn’t the algorithm — it’s the delivery. Candidates who go straight to the HashMap solution often get follow-up questions designed to find out whether they actually understood it or just memorised it. Candidates who walk through brute force first, name the bottleneck, then optimise — they tend to skip those follow-ups and move to the next problem.

Practice this one until you can do it in your sleep with the interview script above. Once you can, you’ll find the same pattern showing up in dozens of other problems: brute force, then trade space for time via a hash structure. Two Sum is the doorway. Everything else is a variation.

Happy coding!