Two Sum

The Two Sum problem requires finding two distinct indices in an array whose corresponding values sum up to a specific target. A naive approach involves checking every possible pair, resulting in quadratic time complexity. However, a more efficient solution leverages a hash map to achieve linear time complexity.

The Problem

Given an array of integers `nums` and an integer `target`, the goal is to return the indices of the two numbers such that they add up to `target`. Each input is guaranteed to have exactly one solution, and the same element cannot be used twice.

How It Works

The core idea is to iterate through the array once, and for each number, determine what 'complement' number would be needed to reach the target. We then check if this complement has already been encountered and stored. A hash map (or dictionary) is ideal for this because it allows for near-constant time lookups.

Step-by-Step Process

1. Initialize Hash Map: Start with an empty hash map, often named `seen`, to store numbers encountered so far along with their indices. 2. Iterate Through Numbers: For each number `num` at `index` in the input array: a. Calculate Complement: Determine the `diff` (the complement) needed to reach the `target` by subtracting the current `num` from `target` (`diff = target - num`). b. Check Hash Map: See if `diff` already exists as a key in the `seen` hash map. i. If `diff` *is* in `seen`, it means we have found the two numbers. The indices are `seen[diff]` (the index of the complement) and the current `index`. ii. If `diff` *is not* in `seen`, add the current `num` and its `index` to the `seen` hash map (`seen[num] = index`). This prepares for future numbers that might need `num` as their complement.

This process continues until the required pair is found and their indices are returned.

function two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i

Key Takeaways

• The Two Sum problem finds two array elements that sum to a target.
• A hash map is used to store numbers and their indices for efficient lookups.
• The algorithm processes the array in a single pass.
• It improves time complexity from O(n^2) to O(n).
• The hash map stores the *value* as the key and its *index* as the value.