Two Sum

Problem Description (Optional Summary)

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

Solution Approach

Use a hash map (dictionary in Python) to store numbers encountered so far and their indices. For each number, check if target - current_number exists in the hash map. If it does, we found the pair. Otherwise, add the current number and its index to the map.

Code

def twoSum(nums: list[int], target: int) -> list[int]:
    numMap = {} # val -> index
    for i, n in enumerate(nums):
        diff = target - n
        if diff in numMap:
            return [numMap[diff], i]
        numMap[n] = i
    return [] # Should not happen based on problem constraints

Complexity Analysis

• Time: O(n) - We iterate through the list once. Hash map lookups/insertions are O(1) on average.
• Space: O(n) - In the worst case, the hash map stores almost all elements.

Notes & Learnings

Classic use case for a hash map to optimize search from O(n) (in a nested loop approach) to O(1). Remember to handle edge cases if the problem constraints allowed for no solution.