Two Sum

📚 Table of Contents

Problem Statement
Real-World Analogy
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Common Mistakes
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

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

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

You can return the answer in any order.

Examples:

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
nums[1] + nums[2] = 2 + 4 = 6

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Same value at different indices is allowed

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists

💡 Solution Approaches

Approach 1: Brute Force

Time: O(N²) | Space: O(1)

Check every possible pair until finding one that sums to target

Python Implementation:

          def two_sum_brute(nums: List[int], target: int) -> List[int]:
    """
    Brute Force: Check all pairs
    Time: O(N²) - nested loops
    Space: O(1) - no extra data structures
    """
    n = len(nums)

    # Try every possible pair
    for i in range(n):
        for j in range(i + 1, n):  # Start j after i to avoid duplicates
            if nums[i] + nums[j] == target:
                return [i, j]

    return []  # No solution found
        

JavaScript Implementation:

          function twoSumBrute(nums, target) {
    /**
     * Brute Force: Check all pairs
     * Time: O(N²) - nested loops
     * Space: O(1) - no extra data structures
     */
    const n = nums.length;

    // Try every possible pair
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {  // Start j after i
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }

    return [];  // No solution found
}
        

Approach 2: Optimal (Hash Map)

Time: O(N) | Space: O(N)

Use hash map to store complements for O(1) lookup

Python Implementation:

          def two_sum(nums: List[int], target: int) -> List[int]:
    """
    Optimal: Hash Map for O(N) solution

    Key Insight: For each number, check if its complement (target - number)
    has been seen before. Hash map gives O(1) lookup.

    Time: O(N) - Single pass through array
    Space: O(N) - Hash map stores up to N elements
    """
    seen = {}  # Maps value → index

    for i, num in enumerate(nums):
        complement = target - num  # What we need to find

        # Check if complement exists in our hash map
        if complement in seen:  # O(1) lookup
            return [seen[complement], i]

        # Store current number for future complement checks
        seen[num] = i  # O(1) insertion

    return []  # No solution found (though problem guarantees one exists)
        

JavaScript Implementation:

          function twoSum(nums, target) {
    /**
     * Optimal: Hash Map for O(N) solution
     *
     * Key Insight: For each number, check if its complement (target - number)
     * has been seen before. Hash map gives O(1) lookup.
     *
     * Time: O(N) - Single pass through array
     * Space: O(N) - Hash map stores up to N elements
     */
    const seen = new Map();  // Maps value → index

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const complement = target - num;  // What we need to find

        // Check if complement exists in our hash map
        if (seen.has(complement)) {  // O(1) lookup
            return [seen.get(complement), i];
        }

        // Store current number for future complement checks
        seen.set(num, i);  // O(1) insertion
    }

    return [];  // No solution found
}
        

🔍 Step-by-Step Walkthrough

Let's trace through the optimal algorithm with a concrete example:

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

            Step 1: i=0, num=2

            - complement = 9 - 2 = 7

            - seen = {}

            - 7 not in seen

            - seen = {2: 0}

            → Store 2 at index 0 for future lookups
          
            Step 2: i=1, num=7

            - complement = 9 - 7 = 2

            - seen = {2: 0}

            - 2 IS in seen! ✓

            - return [0, 1]

            → Found pair: nums[0] + nums[1] = 2 + 7 = 9
          
Result: [0, 1]

⚡ Complexity Analysis

Time Complexity: O(N)

Single pass: iterate through the array once.
Hash-map operations: lookup and insert are O(1) on average.
Per iteration: O(1) work (lookup + optional insertion).
Total: N iterations × O(1) = O(N).

Breakdown

for i, num in enumerate(nums):      # N iterations
    complement = target - num        # O(1)
    if complement in seen:           # O(1) average
        return [seen[complement], i] # O(1)
    seen[num] = i                    # O(1) average

Space Complexity: O(N)

Hash-map storage: up to N elements in worst case.
Extra variables: O(1) for complement, i, num.
Total: O(N) + O(1) = O(N).

Comparison To Brute Force

Approach	Time	Space	Trade-off
Brute Force	O(N²)	O(1)	No extra space, but slower on large inputs.
Hash Map	O(N)	O(N)	Uses memory to achieve linear runtime.

Why this works: the hash map trades space for speed. Instead of re-scanning prior values each time, you check complements in constant time.

🔧 Edge Cases

Comprehensive coverage of edge cases ensures your solution is robust:

Minimum length array
Input: [1, 2], target=3
Output: [0, 1]
Smallest valid input (problem requires at least 2 elements)

Same value used twice (different indices)
Input: [3, 3], target=6
Output: [0, 1]
Duplicates at different positions are allowed

Negative numbers
Input: [-1, -2, -3, -4, -5], target=-8
Output: [2, 4]
-3 + (-5) = -8. Algorithm works with negatives.

Mix of positive and negative
Input: [-3, 4, 3, 90], target=0
Output: [0, 2]
-3 + 3 = 0

Large numbers
Input: [999999999, 1], target=1000000000
Output: [0, 1]
Within constraints: -10⁹ to 10⁹

Target at end of array
Input: [1, 2, 3, 4, 5], target=9
Output: [3, 4]
4 + 5 = 9. Solution can be anywhere in array.

✅ Test Cases

Run these tests to verify your implementation:

Python Test Suite:

          def test_two_sum():
    # Basic cases
    assert two_sum([2, 7, 11, 15], 9) == [0, 1]
    assert two_sum([3, 2, 4], 6) == [1, 2]
    assert two_sum([3, 3], 6) == [0, 1]

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

    # Edge cases
    assert two_sum([1, 2], 3) == [0, 1]  # Minimum length
    assert two_sum([999999999, 1], 1000000000) == [0, 1]  # Large numbers
    assert two_sum([1, 2, 3, 4, 5], 9) == [3, 4]  # End of array

    print("✅ All test cases passed!")

test_two_sum()
        

JavaScript Test Suite:

          function testTwoSum() {
    const assert = (condition, message) => {
        if (!condition) throw new Error(message || "Assertion failed");
    };

    const arraysEqual = (a, b) => JSON.stringify(a) === JSON.stringify(b);

    // Basic cases
    assert(arraysEqual(twoSum([2, 7, 11, 15], 9), [0, 1]));
    assert(arraysEqual(twoSum([3, 2, 4], 6), [1, 2]));
    assert(arraysEqual(twoSum([3, 3], 6), [0, 1]));

    // Negative numbers
    assert(arraysEqual(twoSum([-1, -2, -3, -4, -5], -8), [2, 4]));
    assert(arraysEqual(twoSum([-3, 4, 3, 90], 0), [0, 2]));

    // Edge cases
    assert(arraysEqual(twoSum([1, 2], 3), [0, 1]));
    assert(arraysEqual(twoSum([999999999, 1], 1000000000), [0, 1]));
    assert(arraysEqual(twoSum([1, 2, 3, 4, 5], 9), [3, 4]));

    console.log("✅ All test cases passed!");
}

testTwoSum();
        

⚠️ Common Mistakes

Learn from these frequent errors to write bug-free code:

❌ Mistake #1: Using same index twice

            # ❌ WRONG: Checking complement before updating seen
def two_sum_wrong(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        seen[num] = i  # Add FIRST
        complement = target - num
        if complement in seen:  # Then check
            return [seen[complement], i]

# Problem: If nums = [3, 2, 4], target = 6
# At i=0, num=3, we add 3:0 to seen
# complement = 6-3 = 3
# 3 is in seen! Returns [0, 0] ❌ (same index twice)
          

            # ✅ CORRECT: Check complement BEFORE adding current
def two_sum_correct(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:  # Check FIRST
            return [seen[complement], i]
        seen[num] = i  # Add AFTER checking
          

Why: Always check for complement BEFORE adding current element to avoid using same index twice.

❌ Mistake #2: Not handling "no solution" case

            # ❌ WRONG: No explicit return for no solution
def two_sum_wrong(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    # Falls through, returns None ❌
          

            # ✅ CORRECT: Explicit empty list return
def two_sum_correct(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []  # Explicit: no solution found ✅
          

Why: Always return an empty list (or appropriate value) when no solution exists, even if problem guarantees a solution.

💼 Interview Intel

Frequency: ⭐⭐⭐⭐⭐ (Asked at 90%+ of technical interviews)

Companies Known to Ask:

GoogleAmazonFacebookMicrosoftAppleBloombergUber

Common Follow-Up Questions:

What if the array is sorted? → Two-pointer approach is better (no extra space)
Return all pairs that sum to target? → Modify to collect all, handle duplicates
What if we can use same element twice? → Remove the i+1 check in brute force
What's the space complexity? → O(N) for hash map, discuss tradeoff

What Interviewers Want to See:

Start with brute force approach (shows problem-solving process)
Recognize the complement pattern (target - current)
Identify the optimization: hash map for O(1) lookup
Handle edge cases without prompting
Clearly explain time/space tradeoffs
Write clean, bug-free code on first attempt

🔗 Related Problems & Learning Path

Next Steps (Progressive Learning):

Two Sum II - Input Array Is Sorted (Easy) - Same problem but optimized for sorted input with two pointers
3Sum (Medium) - Extension to finding triplets that sum to zero
4Sum (Medium) - Further extension to four numbers
Valid Anagram (Easy) - Similar hash map pattern for frequency counting

Same Pattern (Different Context):

Subarray Sum Equals K (prefix sums + hash map)
Continuous Subarray Sum (modulo + hash map)
Find All Anagrams in String (sliding window + hash map)

🎓 Key Takeaways

Complement Pattern: for each value, compute what you need (target - current) and check if it's already seen.
Hash Map For O(1) Lookup: trading O(N) space for constant-time lookup drives the speedup.
One Pass Is Enough: process values as you go; you do not need a full pre-pass.
Order Matters: check complement before inserting current value to avoid same-index reuse.

📚 Table of Contents

📋 Problem Statement

Examples:

Constraints:

🎯 Real-World Analogy

💡 Solution Approaches

Approach 1: Brute Force

Python Implementation:

JavaScript Implementation:

Approach 2: Optimal (Hash Map)

Python Implementation:

JavaScript Implementation:

🔍 Step-by-Step Walkthrough

⚡ Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N)

Comparison To Brute Force

🔧 Edge Cases

✅ Test Cases

Python Test Suite:

JavaScript Test Suite:

⚠️ Common Mistakes

❌ Mistake #1: Using same index twice

❌ Mistake #2: Not handling "no solution" case

💼 Interview Intel

Common Follow-Up Questions:

What Interviewers Want to See:

🔗 Related Problems & Learning Path

Next Steps (Progressive Learning):

Same Pattern (Different Context):

🎓 Key Takeaways