deepSWE.io

Two Sum

ArraysHash Table

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers in the array such that they add up to the 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.

Example

11 + 15 = 17

(indices: [2, 3])

Solution Pair

Array Elements

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

Output: [0,1]

Explanation:

nums[0] + nums[1] = 2 + 7 = 9
Therefore, we return [0,1]

Constraints

• 2 ≤ nums.length ≤ 10⁴
• -10⁹ ≤ nums[i] ≤ 10⁹
• -10⁹ ≤ target ≤ 10⁹
• Exactly one valid answer exists
• Same element cannot be used twice

Solution Approaches

• Brute Force: Check every pair (O(n²))
• Hash Table: Store complement values (O(n))
• Two Pointers: If array is sorted (O(n log n))
• Space-Time tradeoff possible

Algorithm Explanation

The Two Sum problem can be solved efficiently using a hash map to store complements of each number as we traverse the array. This allows us to find pairs in a single pass.

Key Steps

Hash Map: Store each number's complement (target - num) as key with its index as value.
Current Number: Check if the current number exists as a key in the map.
Complement: If found, we've found a valid pair that sums to target.
Update Map: If not found, add current number's complement to the map.

Solution Properties

Time Complexity: O(n) - single pass through array
Space Complexity: O(n) - hash map storage
In-place: No modifications to input array
Early termination: Returns as soon as pair is found

Two Sum Visualization

Target Sum: 17

Hash Map

Start: Initialize search

Looking for two numbers that sum to 17

Step 1 of 11

Current Number

Solution Pair

Array Elements

Code Example

def twoSum(nums: List[int], target: int) -> List[int]:
    """
    Find two numbers in the array that add up to target.
    
    Args:
        nums: List of integers
        target: Target sum to find
        
    Returns:
        List of two indices whose values sum to target
        
    Time complexity: O(n) - single pass through array
    Space complexity: O(n) - hash map storage
    """
    # Hash map to store numbers and their indices
    seen = {}
    
    # Check each number
    for i, num in enumerate(nums):
        diff = target - num
        
        # If we've seen a number that adds up to target with current number
        if diff in seen:
            return [seen[diff], i]
            
        # Store current number and its index
        seen[num] = i
        
    return []  # No solution found