Two Sum: The Comprehensive Python Interview Guide

1. Top Coding Interview Question: Two Sum

Question: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

Example:

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

2. Starting with the Brute Force Approach (O(n²))

In a technical interview, it is often perfectly acceptable—and sometimes encouraged—to start with the simplest, most obvious solution. This shows you understand the problem before attempting to optimize it.

The "Brute Force" approach is simple: check every single pair of numbers in the array to see if they add up to the target.

The Algorithm

1. Loop through each number in the list (let's call it x).
2. Loop through every other number after x (let's call it y).
3. If x + y == target, return their indices.

Python Solution (Brute Force)

def two_sum_brute_force(nums, target):
    n = len(nums)
    # Iterate through each element
    for i in range(n):
        # Iterate through the remaining elements
        for j in range(i + 1, n):
            # Check if they sum to target
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Why Optimize?

While correct, this approach is slow.

• Time Complexity: O(n²) because of the nested loops. If the array has 10,000 elements, you might perform
  0,000^2$ (100 million) operations.
• Space Complexity: O(1) as we don't store extra data.

3. The Optimized Approach: O(n)

To optimize, we can ask: "For each number x, what number do we need to reach the target?" we need target - x.

Instead of scanning the rest of the array to find this "needed" number, we can use a Hash Map (Dictionary) to look it up instantly.

The Algorithm

1. Create an empty dictionary seen.
2. Iterate through the array once.
3. For each number num, calculate complement = target - num.
4. Check if complement is already in seen.
   • If yes, we found our pair! Return the index of complement and the current index.
   • If no, add the current num and its index to seen.

Python Solution (Optimized)

def two_sum_optimized(nums, target):
    # Use a hash map to store: number -> index
    seen = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        # Check if complement exists in our hash map (we've seen it before)
        if complement in seen:
            return [seen[complement], i]
        
        # Store current number and its index for future lookups
        seen[num] = i
    
    return []  # Should not happen as per problem statement

Key Concepts for Interviews

• Hash Map / Dictionary: Essential for reducing lookup time from O(n) to O(1).
• Space-Time Tradeoff: We use extra memory (the dictionary) to drastically speed up execution.
• One-Pass Iteration: We solve the problem by looking at each element only once.

Complexity Analysis

• Time Complexity: O(n). We traverse the list exactly once. Dictionary lookups are O(1) on average.
• Space Complexity: O(n). In the worst case, we might store almost every element in the hash map.

4. Master Technical Interviews

The difference between a "hire" and "no hire" often comes down to:

1. Communicating your thought process (Brute Force -> Optimized).
2. Recognizing patterns like Hash Maps.
3. Handling edge cases correctly.

Want to practice these skills in a realistic environment?

Start Your Free Test Interviews on totop.app 🚀

Practice with real-world questions, get instant AI feedback, and land your dream job.