The Two Sum Problem

The Two Sum Problem is one of the first stops on our journey. It’s simple enough to focus on thought process, yet rich enough to demonstrate key problem‑solving techniques. Here’s how to walk through it using our nine‑step framework.

1. Clarify Requirements Before Jumping Into Code

What I Ask the Candidate:

• “Do we always have exactly one valid pair?”

• “Can we use the same array element twice?”

• “Are inputs always integers? Could they be negative?”

• “Should we return indices or values?”

  
  

Why This Matters: Getting these details up front prevents wasted effort on the wrong assumptions. Here are your interviewers answers:

• One solution guaranteed

• No re‑using the same element

• Mixed positive/negative integers allowed

• Return the pair of indices

  
  

2. Identify the Category of the Question

We've got an array of integers and we need to find two elements that sum to a target. My first thought is that we'll be doing a lot of lookups in order to compare integers, and I need those lookups to be fast. That tells me this isn’t just about looping; it’s about choosing the right data structure to support constant‑time checks.

Also, I’m not dealing with sorted order or range queries, so it’s not really a two‑pointer or binary‑search scenario unless I sort. Instead, I want to remember elements as I go and query them quickly—that’s exactly what a hash map (or dictionary) is built for.

So I’d categorize this as a data‑structure problem that leans heavily on hash tables. Recognizing that early helps me zero in on the most efficient approach.

3. Consider a Brute‑Force Approach to Understand the Problem

Let’s start with the simplest idea: check every pair.

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

Takeaways:

• Correctness first: This always works.

• Inefficiency second: It’s O(n²) time—too slow for large inputs.

  
  

4. Brainstorm More Solutions

The brute‑force method works, but O(n²) is going to kill if the array is large. How can I cut down on those nested loops? What if I could remember which numbers I’ve already seen so I don’t have to scan the rest of the array each time?

On each iteration, I have a num. I need to know if there’s another number complement = target - num somewhere earlier in the array. If I could check for that complement in O(1) time, I’d avoid the inner loop entirely. What data structure gives me constant‑time lookups? A hash map!

So here’s the idea: as I iterate, I check if complement in map. If it is, great—I’ve found my pair. If not, I store the current num and its index in the map and move on. That way, every element only gets looked at once, and I end up with an O(n) solution.

Could I sort the array and use a two‑pointer approach? Sure, but sorting is O(n log n), so it’s slower than the hash‑map method for a one‑pass solution.

I’m leaning strongly toward the hash map approach because it keeps things simple and efficient—just one pass, one data structure, and we’re done.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute‑Force	O(n²)	O(1)	Simple to write	Too slow for big n
Hash Map (One‑Pass)	O(n)	O(n)	Fast, single pass	Uses extra memory
Two‑Pointer*	O(n log n)	O(1)	In‑place, low extra memory	Requires sorting (loses index order)

*Only if you sort or have a copy of the array.

Key Discussion Points:

• We trade off extra space for speed.

• Sorting helps a two‑pointer solution, but sorting is slower than the hash map solution

  
  

6. Write Pseudocode to Structure Your Thoughts

function twoSum(nums, target):
    create empty map: num_to_index

    for index, num in nums:
        complement = target - num
        if complement exists in num_to_index:
            return [num_to_index[complement], index]
        store num_to_index[num] = index

7. Consider Edge Cases

• Empty array: Should return [] or an error.

• Single element: No valid pair—handle gracefully.

• No solution: Depending on spec, return None, [], or throw an exception.

• Negative numbers and zeros: Works seamlessly with the hash map approach.

• Duplicate values: Map will store the most recent index; ensure you find the correct pair order.

  
  

8. Write Full Code Syntax

def two_sum(nums, target):
    num_to_index = {}

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

    # If no pair found (depending on requirements):
    return []

9. Test Your Code

# 1. Standard case
assert two_sum([2, 7, 11, 15], 9) == [0, 1]

# 2. Negative numbers
assert two_sum([-3, 4, 3, 90], 0) == [0, 2]

# 3. Duplicates
assert two_sum([3, 3], 6) == [0, 1]

# 4. No solution
assert two_sum([1, 2, 3], 7) == []

# 5. Edge cases
assert two_sum([], 5) == []
assert two_sum([5], 5) == []

Final Thoughts

By walking through these nine steps—from clarifying requirements to testing your solution—you not only arrive at a correct, efficient answer but also showcase your structured approach to problem‑solving. Keep practicing this framework, and you’ll be ready to tackle Two Sum and its more complex cousins with confidence in your next technical interview.

Happy coding!