Two Sum

Problem Statement

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.

You can return the answer in any order.

Examples

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 6, we return [0, 1].

Constraints

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

Approach 1: Hash Map (Optimal)

Algorithm

Use a hash map to store numbers and their indices for O(1) lookup.

Steps:

1. Create a hash map to store number -> index mapping
2. For each number in the array:
   • Calculate complement = target - current number
   • If complement exists in hash map, return indices
   • Otherwise, store current number and its index in hash map

Implementation

Python:

def twoSum(nums, target):
    """
    Find two numbers that add up to target using hash map
    Time: O(n)
    Space: O(n)
    """
    num_map = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        if complement in num_map:
            return [num_map[complement], i]
        
        num_map[num] = i
    
    return []  # No solution found

Java:

import java.util.*;

class Solution {
    /**
     * Find two numbers that add up to target using hash map
     * Time: O(n)
     * Space: O(n)
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            
            numMap.put(nums[i], i);
        }
        
        return new int[]{}; // No solution found
    }
}

Go:

func twoSum(nums []int, target int) []int {
    /**
     * Find two numbers that add up to target using hash map
     * Time: O(n)
     * Space: O(n)
     */
    numMap := make(map[int]int)
    
    for i, num := range nums {
        complement := target - num
        
        if idx, exists := numMap[complement]; exists {
            return []int{idx, i}
        }
        
        numMap[num] = i
    }
    
    return []int{} // No solution found
}

JavaScript:

/**
 * Find two numbers that add up to target using hash map
 * Time: O(n)
 * Space: O(n)
 */
function twoSum(nums, target) {
    const numMap = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        
        numMap.set(nums[i], i);
    }
    
    return []; // No solution found
}

C#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find two numbers that add up to target using hash map
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int[] TwoSum(int[] nums, int target) {
        var numMap = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            
            if (numMap.ContainsKey(complement)) {
                return new int[] { numMap[complement], i };
            }
            
            numMap[nums[i]] = i;
        }
        
        return new int[] {}; // No solution found
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through array
• Space Complexity: O(n) - Hash map storage

Key Insights

1. Hash Map Approach: Most efficient with O(n) time complexity
2. Two Pointers: Alternative approach with O(n log n) time complexity
3. Complement Strategy: Look for target - current number
4. Index Preservation: Maintain original indices in two pointers approach
5. Single Pass: Hash map approach processes array only once

Edge Cases

1. No Solution: Handle case where no two numbers sum to target
2. Duplicate Values: Handle arrays with duplicate numbers
3. Negative Numbers: Handle negative numbers correctly
4. Zero Target: Handle target sum of zero
5. Two Elements: Handle arrays with exactly two elements

Test Cases

def test_twoSum():
    # Test case 1: Normal case
    nums1 = [2, 7, 11, 15]
    target1 = 9
    result1 = twoSum(nums1, target1)
    expected1 = [0, 1]
    assert result1 == expected1
    
    # Test case 2: Different indices
    nums2 = [3, 2, 4]
    target2 = 6
    result2 = twoSum(nums2, target2)
    expected2 = [1, 2]
    assert result2 == expected2
    
    # Test case 3: Duplicate values
    nums3 = [3, 3]
    target3 = 6
    result3 = twoSum(nums3, target3)
    expected3 = [0, 1]
    assert result3 == expected3
    
    # Test case 4: Negative numbers
    nums4 = [-1, -2, -3, -4, -5]
    target4 = -8
    result4 = twoSum(nums4, target4)
    expected4 = [2, 4]
    assert result4 == expected4
    
    print("All tests passed!")

test_twoSum()

Follow-up Questions

1. Two Sum II: Handle sorted array?
2. Two Sum III: Design data structure for two sum?
3. Two Sum IV: Find two sum in BST?
4. Two Sum with Constraints: Add additional constraints?
5. Two Sum with Duplicates: Handle duplicate values differently?

Common Mistakes

1. Same Element Twice: Using same element twice for sum
2. Index Order: Returning indices in wrong order
3. Hash Map Key: Using wrong key in hash map
4. Edge Cases: Not handling no solution case
5. Time Complexity: Not optimizing from O(n²) to O(n)

Interview Tips

1. Start with Brute Force: Show understanding of the problem
2. Optimize with Hash Map: Explain hash map approach
3. Handle Edge Cases: Mention duplicate values and no solution
4. Discuss Trade-offs: Compare time vs space complexity
5. Follow-up Ready: Be prepared for variations and optimizations

Concept Explanations

Two Sum: We need to find two numbers in an array that add up to a target value and return their indices.

Hash Map Approach: We use a hash map to store numbers and their indices. For each number, we calculate its complement (target - current number) and check if it exists in the hash map.

Complement Strategy: Instead of looking for two numbers that sum to target, we look for one number and its complement. This reduces the problem to a single lookup.

Why Hash Map Works: The hash map provides O(1) lookup time, making the overall algorithm O(n) instead of O(n²) brute force.

Space-Time Trade-off: The hash map approach uses O(n) extra space to achieve O(n) time complexity, which is a good trade-off for this problem.

Edge Case Handling: We need to handle cases where no solution exists, duplicate values, and negative numbers correctly.