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.

Problem Statement

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

You may assume that exactly one solution exists, and you may not use the same element twice.

Return the answer in any order.

Example:

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

Explanation: nums[0] + nums[1] == 9

1. Clarify Requirements Before Jumping Into Code

As always, let's start by clarifying some details with the interviewer:

• One solution is guaranteed

• No re‑using the same element

• Mixed positive/negative integers in the input are 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

Option 1: Hash Map

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.

Option 2: Sort

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

But, having a sorted array does present an interesting solution that's worth talking about. When my array is sorted I know exactly how my elements are going to change as I iterate through - they will increase as I move up, and they will decrease as I move down.

How can I combine that knowledge with the two-pointer technique?

• I'll start by placing one pointer on the left and the other pointer on the right.

• If my sum of those two elements is too big, then I can decrease the right pointer.

• If my sum is too small, then I increase the right pointer.

• I keep going until I either find a pair that matches my target, or the two pointers cross

At every iteration, I am inching closer to my target sum, a solution that is only possible because my array is sorted. If a complement exists, I can find it O(n) time!

Buuuut since I don't have a sorted array, the hash map approach is best. 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) == []

10. Lessons Learned

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!