blind-75

Two Sum

Best Case: The best case occurs when the first two elements of the array sum to the target.
Worst Case: The worst case occurs when no two elements sum to the target, requiring a full traversal of the array.

Approach:

1. Use a hash map to store the difference between the target and each element as you iterate through the array.
2. For each element, check if it exists in the hash map.

Explanation to Interviewer:
“In solving the Two Sum problem, I would use a hash map to track the required complements of each number as I iterate through the list. This allows me to check for pairs in linear time.”

Code Implementation:

JavaScript:

function twoSum(arr, target) {
    const map = new Map();
    for (let i = 0; i < arr.length; i++) {
        const complement = target - arr[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(arr[i], i);
    }
    return [];
}

const arr = [0, -1, 2, -3, 1];
const target = -2;
console.log(twoSum(arr, target)); // Output: [0, 2]

Python:

def two_sum(arr, target):
    num_map = {}
    for i, num in enumerate(arr):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

arr = [0, -1, 2, -3, 1]
target = -2
print(two_sum(arr, target))  # Output: [0, 2]