Thinking clearly in interviews — Two Sum

Understanding the why before the code (Rust · Python · Scala)

⚠️ Before we dive in — highly worth your attention

Lights On by Farida Khalaf - a publication where systems thinking meets real-world AI and business insights. Farida breaks down complexity into clarity, with frameworks and perspectives that make tech trends feel actionable rather than overwhelming.

---

You’re standing in a small market with a basket in one hand and a short list in the other. You remember you have a coupon that takes exactly a fixed amount off - say, $9 - but it only applies if you buy two items whose prices add up to that amount. Easy, you think: just glance at the tags and find a pair.

Then the mild confusion starts. There are more items than you expected. Some prices repeat. A few are even discounted in odd ways, so the same number shows up again and again. You catch yourself circling the same shelf twice, picking up an item, putting it back, and wondering if you already considered it. The problem isn’t that anything is “wrong” - it’s that your brain is doing a very human thing: searching without a system.

Nothing is broken here. This is what happens when the space of possibilities grows: what felt like a quick visual match turns into a process problem. And process problems are exactly what coding interviews are designed to surface - not whether you’ve seen a trick before, but whether you can turn a fuzzy search into a clean, explainable method.

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Examples

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Constraints

You may assume that each input would have exactly one solution, and you may not use the same element twice.

The Two Sum problem is that market moment, translated into arrays and indices. The best solutions don’t come from moving faster; they come from deciding what you’re going to remember as you scan, and how you’ll prove to yourself (and an interviewer) that you didn’t miss anything.

🎙️ Why is it so interesting

From an interviewer’s perspective, Two Sum is deceptively small. The statement fits in a couple of lines, the examples look friendly, and most candidates feel they “basically get it” within seconds. That’s exactly why it works: it creates a situation where it’s easy to start coding before you’ve demonstrated good engineering judgment.

A strong interviewer isn’t looking for whether you can add two numbers. They’re watching for whether you can do a few higher-signal things under light time pressure:

• You clarify what must be returned. Many candidates jump to returning the numbers themselves, not their indices. That’s not a tiny mistake; it indicates you’re not anchoring on requirements.

• You manage ambiguity proactively. What about duplicates? Can the same element be used twice? Is there always a solution? These questions change the shape of the code, and interviewers want to see you surface those constraints instead of stumbling into them mid-implementation.

• You reason about trade-offs. Two Sum has a clean naive solution and a clean optimized solution. Interviewers want to see if you can explain both, choose appropriately given constraints, and justify the complexity out loud.

• You implement carefully. The “optimal” idea is simple - a hash map lookup - but it’s also easy to get wrong with off-by-one mistakes, wrong insertion order, or duplicate handling. That’s the point: can you write correct, readable code while narrating your reasoning?

Two Sum is also a gateway. The same mental pattern shows up everywhere: “I’m scanning a list; what facts do I need to remember so I can decide quickly when I see the next element?” If you can communicate that pattern well here, you’re building interview leverage for a whole family of problems.

📖 Understanding the problem in plain language

You’re given a list of integers and a target integer. You need to find two different positions in the list such that the values at those positions add up exactly to the target.

The output is not the values - it’s the indices (positions) of the two elements. The order of the returned indices usually doesn’t matter unless explicitly stated, but you should be consistent.

A few constraints matter a lot:

• There is exactly one valid answer. That means you don’t have to return all pairs, and you don’t have to deal with “no solution” unless the interviewer extends the problem.

• You may not use the same element twice. If the target is 10 and the array contains a single 5, you can’t use that one 5 two times. But if the array contains two 5s at different indices, then you can use those two distinct elements.

• Values can be negative, zero, or repeated, unless otherwise restricted. Many candidates subconsciously assume “positive and distinct” because the examples look that way. Don’t.

When I restate this to a colleague, I usually say:

“Scan this array and return the two positions i and j (i ≠ j) where nums[i] + nums[j] == target.”

That restatement is important because it highlights the real work: you’re not doing arithmetic, you’re doing search, and you’re doing it while preserving original positions.

👣 Reasoning through examples

Let’s walk slowly through the classic example:

• nums = [2, 7, 11, 15]

• target = 9

A good candidate narrates something like:

“I need two indices. If I pick 2 at index 0, I need 7 to reach 9. Is 7 present later? Yes - index 1. So the answer is [0, 1].”

That’s correct, but the interviewer wants more than correctness on the toy input. They want to hear a process that scales.

Here’s the more interview-useful narration:

“As I scan left to right, for each number x I can compute its complement c = target - x. If I’ve already seen c earlier, then I’ve found the pair: the earlier index of c and the current index. If not, I store x with its index for future lookups.”

Now you’ve described an algorithm, not just an observation.

Let’s test the narration on something slightly trickier:

• nums = [3, 3]

• target = 6

If you store the first 3 at index 0, then when you see the second 3 at index 1, the complement is also 3, which you’ve seen. You return [0, 1]. This example is important because it proves you understand “not the same element twice” really means “not the same index twice”.

Another example that reveals common misunderstandings:

• nums = [1, 5, 1, 5]

• target = 6

There are many value matches, but the problem guarantees exactly one solution in the test setup. Still, your code should behave sensibly with duplicates. If you use a hash map of value → index, you have to decide: do you store the first index, the last index, or does it matter? It can matter if the complement equals the current value (like 3 and 3), or if the “one solution” guarantee is removed as a follow-up.

The key is: your reasoning needs to explicitly connect “what I store” with “what I will look up later”, and that connection should remain correct even when values repeat.

📏 Constraints and what they tell us

Interview constraints are often understated, but Two Sum is one of those problems where constraints quietly dictate the right approach.

If the array length n is small (say, a few hundred), an O(n²) solution is perfectly fine in production and fine in many interviews. But interviews rarely choose Two Sum for n=200. They choose it because they want to see whether you recognize that O(n²) becomes painful when n is large - tens of thousands, hundreds of thousands, or more.

The “exactly one solution” constraint is also a hint. It tells you:

• You can return as soon as you find a valid pair.

• You don’t need to keep searching for alternatives.

• You don’t need to worry about tie-breaking.

The “may not use the same element twice” constraint is a bigger hint than it looks. It forces you to think about timing:

• If you build a map of all values first and then search, you must be careful not to pair an element with itself unless there are duplicates.

• If you scan left-to-right and only allow matches with previously seen values, you automatically avoid using the same index twice. That’s a very clean correctness argument, and interviewers like correctness arguments that are easy to say out loud.

Finally, the fact that you must return indices (not values) tells you you can’t sort the array without extra work, because sorting destroys original positions. You can sort if you carry indices along, but that’s already a signal: “I’m choosing a more complex approach than necessary”.

Constraints are the interviewer quietly telling you what kind of thinking they want to see: time complexity awareness, careful handling of duplicates, and a solution that preserves index identity.

🤔 The obvious first idea — and why it’s not enough

The most natural approach is brute force:

• For each index i

• For each index j > i

• Check if nums[i] + nums[j] == target

• If yes, return [i, j]

This is the algorithm your brain does in the market when you keep re-checking shelves: try a choice, then try to match it with every other choice.

Why it feels good:

• It’s simple.

• It’s hard to get wrong.

• It doesn’t require any extra data structure.

• The code is short and readable.

Why it’s not enough (in many interviews):

Time complexity is O(n²). If n = 100,000, that’s ~5 billion pairs in the worst case. Even if each check is fast, that’s not going to finish in a reasonable time.

More subtly, brute force doesn’t demonstrate the interview skill this problem is testing: the ability to reduce search using memory. An interviewer might accept brute force as a starting point, but they’re hoping you’ll quickly move to something better and explain why it’s better.

In a live setting, a strong move is:

• State the brute force approach clearly.

• Give its complexity.

• Then say, calmly: “We can do better by trading space for time.”

That last sentence is the hinge. It signals you understand that performance improvements usually come from changing what you remember, not from writing clever arithmetic.

💡 The key insight

Two Sum becomes easy when you stop thinking of it as “find two numbers” and start thinking of it as:

“As I scan, what information would make the next decision instant?”

Suppose you’re currently at value x. You want to know if there exists a previous value y such that y + x == target. Rearranged:

y == target - x

So the decision at x reduces to a question you can answer instantly if you have the right memory:

“Have I seen (target - x) before? If yes, where?”

That suggests a hash map (dictionary) keyed by value, storing the index where you saw it.

The insight has two important parts:

• Complement thinking: Every element defines exactly what it needs from the past (the complement).

• One-pass memory: If you store what you’ve seen so far, you can decide in O(1) average time per element.

This is not about memorizing that “Two Sum uses a hash map”. It’s about noticing a pattern: you don’t need to search all pairs if you can transform the question into membership queries against a set of prior observations.

In interviews, it’s worth saying explicitly:

“I’m going to scan left to right. For each element, I’ll check whether its complement is already in the map. If it is, I return immediately. Otherwise I insert the current element with its index.”

That’s the moment the interviewer relaxes a bit - because now they can evaluate execution, not direction.

---

💡 Did this mental shift click for you?

What was your “aha” moment while reading this?

💬 Leave a comment - I’d love to know how you think about Two Sum.

---

⚙️The final approach

Narratively, here’s the algorithm:

You keep a dictionary seen that maps a number value to the index where you saw it.

Then for each index i and value x = nums[i]:

• Compute c = target - x

• If c is in seen, you found the answer: [seen[c], i]

• Otherwise store seen[x] = i and continue

Correctness, in words you can say live:

• If the answer uses indices (p, q) with p < q, then when we reach q in the scan, we have already inserted nums[p] into seen.

• At q, we compute complement target - nums[q], which equals nums[p], so the lookup succeeds and we return (p, q).

• We never use the same element twice because we only match the current index with a strictly earlier index from the map.

Edge behavior:

• Duplicates are naturally handled because values can appear multiple times; when the second instance appears, it can match the first if needed.

• The only nuance is whether you store the first occurrence or overwrite with the last. With the “exactly one solution” guarantee, either often works, but storing the first occurrence makes the behavior more stable when duplicates exist and the guarantee is removed.

A small but important implementation detail:

Check for the complement before inserting the current value. That ordering prevents pairing an element with itself when x == target - x. For example, target 6 and x 3: you want to match with a previous 3, not the one you’re currently at.

That check-then-insert rhythm is the cleanest version to explain and defend.

⏱️ Performance under interview constraints

Time complexity:

• You do a single pass through n elements.

• Each pass does a hash lookup and possibly an insert.

• On average, those are O(1), so total is O(n) average time.

Space complexity:

• In the worst case you store each element in the map: O(n) space.

In an interview, you don’t need to over-lawyer the hash table details, but you should be able to say one sentence acknowledging reality:

“This is O(n) average time using a hash map; worst-case hash behavior exists in theory, but in practice and in typical interview models we treat it as constant-time expected operations.”

Trade-offs you can mention calmly:

• If memory is constrained, you might consider sorting with indices (O(n log n) time, O(n) space for the index pairs) and using two pointers, but it’s more code and more ways to slip.

• If you need all pairs (a common follow-up), the map approach needs adjustment because “return immediately” is no longer correct, and duplicates must be counted carefully.

The point is not to recite complexities. The point is to show you can connect code structure to performance with confidence.

💻 Implementation

Implementation is secondary to clarity of thought - but in interviews, “secondary” still means “must be correct”.

Two Sum is a great place to practice readable implementation under time pressure:

• Use descriptive names (seen, complement).

• Keep control flow linear.

• Return early when you find the pair.

• Make the “check then insert” ordering explicit.

Below are reference implementations in Python, Rust, and Scala. Each is written in a style that’s easy to explain while typing.

🐍 Python implementation

Python makes the core idea very direct: a dictionary from value to index.

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    # Maps value -> index where it was seen
    seen = {}

    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]

        # Store AFTER checking, to avoid using the same element twice
        seen[x] = i

    # With the usual constraint “exactly one solution”, we never reach here.
    raise ValueError(”No valid pair found”)

What to explain out loud while coding:

• “seen stores numbers we’ve already passed, along with their indices.”

• “At each number x, I compute the complement and see if it’s already in seen.”

• “If yes, return the earlier index and the current index.”

• “Then I insert x for future elements.”

Common Python nuance:

If the interviewer asks about duplicates, you can say: “This stores the latest index for each value because we overwrite. With the ‘exactly one solution’ guarantee it’s fine; if we wanted the earliest index consistently, we could only insert when the value is not already present.”

If you want that “earliest index” behavior, it’s a one-line change:

if x not in seen:
    seen[x] = i

But don’t add it unless you need it - extra branching is extra surface area for mistakes.

🦀 Rust implementation

Rust is where candidates often get tangled - not because the algorithm changes, but because they start thinking about ownership before they’ve stabilized the control flow.

The trick is to keep it simple:

• Use std::collections::HashMap<i32, usize>

• Iterate with enumerate()

• Look up by reference (get(&complement))

• Return indices as Vec<usize> or Option<(usize, usize)>

Here’s a clean version that returns a pair as Option<(usize, usize)>:

use std::collections::HashMap;

pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();

    for (i, &x) in nums.iter().enumerate() {
        let complement = target - x;

        if let Some(&j) = seen.get(&complement) {
            return Some((j, i));
        }

        // Insert after checking to avoid using the same index twice
        seen.insert(x, i);
    }

    None
}

What’s worth calling out in Rust:

• nums.iter().enumerate() gives (usize, &i32). We pattern-match &x to copy the i32 out (cheap and simple).

• seen.get(&complement) returns Option<&usize>. We match Some(&j) to copy the index out.

• We insert with seen.insert(x, i) after the check.

If you’re asked to match a typical “always exactly one solution” signature, you can unwrap (or panic) at the end, but I prefer returning Option because it keeps the function honest:

pub fn two_sum_strict(nums: &[i32], target: i32) -> (usize, usize) {
    two_sum(nums, target).expect(”Exactly one solution was assumed”)
}

Interviewers generally like when you separate “core algorithm” from “assumptions about input”, because it signals clean engineering instincts.

🟣 Scala implementation

Scala gives you a couple of choices: immutable maps (rebuilding each time) or a mutable map (most interview-friendly here). For a one-pass O(n) scan, a mutable HashMap is straightforward.

import scala.collection.mutable

object TwoSum {
  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val seen = mutable.HashMap[Int, Int]()  // value -> index

    for (i <- nums.indices) {
      val x = nums(i)
      val complement = target - x

      seen.get(complement) match {
        case Some(j) => return Array(j, i)
        case None    => seen.update(x, i)
      }
    }

    // Under the usual constraint “exactly one solution”, this won’t happen.
    throw new IllegalArgumentException(”No valid pair found”)
  }
}

Scala design notes you can mention:

• nums.indices is a clean way to iterate indices without manual bounds.

• seen.get(complement) returns an Option[Int], which we pattern match.

• return is used here intentionally for early exit. In purely functional Scala you might avoid return, but in interviews clarity beats purity - especially for a simple search with an early success condition.

If your interviewer prefers expression-oriented style, you can still keep it readable, but don’t contort yourself. Two Sum is not the place to prove you can write clever Scala.

⚠️ Common interview mistakes

Two Sum is famous, which means interviewers have seen every possible self-inflicted wound. The good news is that most mistakes are predictable.

A very common mistake is returning the values, not the indices. This usually happens when the candidate starts coding before restating the problem. The fix is procedural: always say “indices” out loud before you type your function signature.

Another common mistake is using the same element twice by inserting before checking. The buggy pattern looks like:

• insert x at index i

• check whether complement exists (it will - because you just inserted x)

• accidentally return (i, i) when x * 2 == target

This is why “check then insert” is not just a detail - it’s a correctness guarantee you can explain in one sentence.

Duplicates cause another class of bugs. Candidates sometimes store a value → index map built from the whole array first, then do a second pass. That can work, but it forces you to handle the “don’t use same index” rule explicitly:

• If complement equals x, you must ensure the stored index is not i.

• If there are duplicates, you might overwrite the index you actually need.

That two-pass approach isn’t wrong, but it’s more complicated to reason about live, which makes it a riskier interview choice.

Finally, some candidates overcomplicate by sorting and using two pointers. That solution can be made correct by sorting (value, originalIndex) pairs, but it’s longer, easier to get wrong, and harder to narrate under time pressure. Unless the interviewer explicitly removes the hash map option (rare), sorting is usually not your best first move.

The meta-lesson: in interviews, prefer solutions that are easy to defend, not just easy to code.

---

⚠️ Know someone preparing for interviews?

Send this to them - it might save them from an avoidable mistake.

🔁 Share this post with a friend grinding interview prep.

---

🔍 Edge cases interviewers love to ask about

Once you produce the O(n) hash map solution, interviewers often probe whether you understand what makes it correct by twisting the input slightly.

Duplicates where the pair uses the same value twice:

• nums = [3, 3], target = 6

• Correct output must reference two different indices.

If your code inserts before checking, you’ll fail here. If you check first, you’ll succeed.

Negative numbers and zero:

• nums = [-1, -2, -3, -4, -5], target = -8 → indices for -3 and -5

• nums = [0, 4, 3, 0], target = 0 → indices for the two zeros

This probes whether you accidentally assume positivity or uniqueness.

Very large arrays:

This is less about correctness and more about whether you can justify complexity. Interviewers want to hear: “O(n) time, O(n) space” without hesitation, and they want you to connect the dots: “We store at most one entry per element”.

“What if there is no solution?”:

Even though the prompt says there is exactly one, interviewers often ask this to see if you can design a robust API. In Python you might raise an exception; in Rust you might return Option; in Scala you might return Option[Array[Int]] or throw. The key is to separate: “Given the constraint, we can assume success” from “In production, I’d encode the possibility of failure”.

“What if there are multiple solutions?”:

Now your early return behavior is no longer correct if the task is “return all pairs”. You’d need to collect results, and duplicates become tricky (you might need counts rather than indices, or a different approach entirely). The right response is calm: “The current algorithm returns the first pair it finds; if you need all pairs, the requirements change and we need to redesign”.

Edge cases aren’t a trap; they’re a conversation about whether you understand why your approach works.

🎓 What this problem trains you to do

Two Sum trains a skill that matters far more than this one question: turning pairwise search into single-pass decision-making.

The reusable mental model is:

• I’m scanning items in order.

• At each item, I can compute what I wish I had seen earlier.

• If I record what I’ve seen in a structure optimized for membership tests, I can avoid nested loops.

That model reappears in many forms:

• Variants like “find a pair with difference k” (same complement idea).

• “Three sum” style problems (where you often fix one element and reduce to Two Sum).

• Subarray sum problems (prefix sums + hash maps are the same “remember what matters” move).

• Any streaming scenario where you can’t afford to revisit all prior data.

But the deeper interview takeaway is communication discipline:

• Restate requirements precisely.

• Name the naive solution and its cost.

• Introduce the key insight as a trade: space for time.

• Keep the implementation aligned with the correctness story (“check then insert”).

If you can do that smoothly on Two Sum, you’re not just solving a problem - you’re demonstrating the exact style of thinking interviewers trust.

🌱 Closing thoughts

Two Sum looks simple, which is why it’s such a good interview mirror. It reflects whether you can slow down just enough to be precise, then speed up with a method that stays correct when the input stops being friendly.

When you practice, don’t time yourself on typing. Time yourself on clarity: can you explain, in plain language, what you’re storing, why you’re storing it, and why that guarantees you won’t miss the answer? If you can, the code almost writes itself - and when it doesn’t, you’ll know exactly which invariant you’re trying to preserve.

---

🧠 If you want to build real interview intuition…

I write deep, calm breakdowns of classic problems - without tricks or memorization.

📬 Subscribe to get the next one directly.