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 10,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. Two Sum Variations Interviewers Ask as Immediate Follow-Ups

In almost every technical screen, solving the classic O(n) Hash Map Two Sum is only the first 10 minutes of the round. Interviewers immediately mutate the constraints to test whether you understand the trade-offs between hash tables, sorting + two pointers, and streaming memory bounds:

Follow-Up Code: Two Sum II (When Interviewers Forbid Extra Memory)

If the interviewer asks "Now suppose the array is sorted and you cannot allocate a Hash Map", switch immediately to converging two pointers:

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1   # Need a larger sum
        else:
            right -= 1  # Need a smaller sum
    return []

Critical Edge Cases to Mention Before Submitting

1. Duplicate Elements: If nums = [3, 3] and target = 6, verify that your hash map checks complement in seen before overwriting seen[num] = i, otherwise you will overwrite index 0 with index 1 and fail to return [0, 1].
2. Self-Reuse Prevention: Never use the same array index twice (e.g., nums = [3, 2, 4], target = 6 must not match 3 + 3 at index 0).
3. Integer Overflow (in C++ / Java): When summing two large 32-bit signed integers in Two Sum II, numbers[left] + numbers[right] can overflow INT_MAX; use long or check numbers[left] > target - numbers[right].

Escalation to 3Sum: Why Sorting + Two Pointers Beats a Hash Set

When the interviewer escalates Two Sum to 3Sum ("Find all unique triplets [a, b, c] in nums that sum to 0"), candidates often try to reuse a Hash Set—only to get bogged down deduplicating triplet permutations. Instead, sort the array first in O(n log n) time, iterate i from 0 to n - 3, and run Two Sum II's converging left and right pointers on i + 1 .. n - 1:

• Skip duplicate anchor values whenever i > 0 and nums[i] == nums[i - 1].
• Whenever nums[i] + nums[left] + nums[right] == 0, record the triplet and advance left while nums[left] == nums[left - 1].
• If nums[i] > 0, break immediately—since the array is sorted, no three positive numbers can sum to 0. This reduces overall time complexity to O(n^2) with O(1) auxiliary space beyond the sort.
• Streaming / 100 GB Follow-Up: When asked how Two Sum changes if the input is a 100 GB log file on disk that cannot fit into a 4 GB RAM container, explain how to hash-partition values into K = 64 disk buckets using hash(x) % K (ensuring x and target - x map to deterministic partner buckets) or run an external merge sort followed by two streaming file cursors.
• Two Sum IV (Input is a Binary Search Tree): If the input is a BST of N nodes and memory is constrained to O(H) where H is tree height, create two iterative generators—an inorder stack yielding smallest-to-largest values and a reverse-inorder stack yielding largest-to-smallest values—and step them toward each other exactly like Two Sum II in O(N) time and O(H) space!
• Returning All Unique Pairs vs. Returning Indices: Always clarify whether the interviewer wants the original array indices or the unique value pairs. If original indices are required, you cannot sort the array in place without first pairing each value with its original index tuple, because sorting destroys the initial index positions and shifts every element!

5. 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.