Problem Description

You are given an array of integers nums and an integer value target. Your task is to find two numbers in the array that add up to the target value and return their indices.

The problem guarantees that there will be exactly one valid solution - meaning there's exactly one pair of numbers that sum to the target. You cannot use the same element twice (you need two different positions in the array).

For example:

• If nums = [2, 7, 11, 15] and target = 9
• The numbers at index 0 (2) and index 1 (7) add up to 9
• So you would return [0, 1]

The indices can be returned in any order - [0, 1] and [1, 0] are both acceptable answers.

The solution uses a hash table to efficiently find the pair. As we iterate through the array, for each number x, we check if target - x exists in our hash table. If it does, we've found our pair and return their indices. If not, we store the current number and its index in the hash table for future lookups.

Intuition

The naive approach would be to check every pair of numbers using nested loops, which would take O(n²) time. But we can do better by thinking about what we're actually looking for.

When we're at a number x in the array, we need to find if there's another number that equals target - x. Instead of searching through the entire array each time, we can remember the numbers we've already seen.

The key insight is that for any number x, its complement y = target - x is the exact value we need to find. If we've seen y before in our traversal, then x + y = target and we have our answer.

This leads us to use a hash table (dictionary) to store numbers we've already processed along with their indices. As we traverse the array:

1. For each number x, we calculate what we need: y = target - x
2. We check if y exists in our hash table (meaning we've seen it before)
3. If yes, we found our pair! Return the stored index of y and the current index
4. If no, store x and its index in the hash table for future lookups

This way, we only need one pass through the array, reducing the time complexity to O(n) while using O(n) extra space for the hash table. We're essentially trading space for time - a common optimization technique.

Solution Approach

The solution uses a hash table to achieve linear time complexity. Here's how the implementation works step by step:

We initialize an empty dictionary d to store the numbers we've seen along with their indices. The key will be the number itself, and the value will be its index in the array.

We iterate through the array using enumerate(nums) to get both the index i and the value x at each position:

1. Calculate the complement: For the current number x, we calculate y = target - x. This is the value we need to find to make the sum equal to target.

2. Check if complement exists: We check if y is already in our dictionary d. If it exists, it means we've previously encountered a number that, when added to our current number x, equals the target.

3. Return the result: If we find y in the dictionary, we immediately return [d[y], i], where d[y] is the index of the complement we stored earlier, and i is the current index.

4. Store current number: If the complement is not found, we store the current number and its index in the dictionary as d[x] = i. This allows future iterations to find this number as a potential complement.

The algorithm guarantees we'll find the answer in a single pass because:

• When we encounter the first number of the pair, we store it
• When we encounter the second number of the pair, we'll find the first one already stored in the hash table
• The problem guarantees exactly one solution exists

Time Complexity: O(n) - we traverse the array once
Space Complexity: O(n) - in the worst case, we might store almost all elements in the hash table before finding the pair

Example Walkthrough

Let's walk through the solution with nums = [2, 7, 11, 15] and target = 9.

We start with an empty hash table d = {}.

Iteration 1 (i=0, x=2):

• Calculate complement: y = 9 - 2 = 7
• Check if 7 exists in d: No, it's empty
• Store current number: d = {2: 0}
• Continue to next iteration

Iteration 2 (i=1, x=7):

• Calculate complement: y = 9 - 7 = 2
• Check if 2 exists in d: Yes! It's at index 0
• Found our pair: Return [d[2], 1] = [0, 1]

The algorithm finds the answer in just 2 iterations. When we encounter 7, we realize we've already seen its complement 2 at index 0, so we immediately return the indices [0, 1].

Let's consider another example to see how the hash table builds up: nums = [3, 2, 4] and target = 6.

Iteration 1 (i=0, x=3):

• Complement: y = 6 - 3 = 3
• Check d for 3: Not found
• Store: d = {3: 0}

Iteration 2 (i=1, x=2):

• Complement: y = 6 - 2 = 4
• Check d for 4: Not found
• Store: d = {3: 0, 2: 1}

Iteration 3 (i=2, x=4):

• Complement: y = 6 - 4 = 2
• Check d for 2: Found at index 1!
• Return [1, 2]

Notice how we build up the hash table as we go, and the moment we find a complement that exists in our hash table, we have our answer.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once in the worst case. Each iteration performs constant-time operations: checking if a key exists in the dictionary (O(1) average case for hash table lookup), dictionary insertion (O(1) average case), and arithmetic operations.

The space complexity is O(n), where n is the length of the array nums. In the worst case, when no two numbers sum to the target until the last possible pair, the algorithm stores n-1 elements in the dictionary d. The dictionary stores key-value pairs where keys are the numbers from nums and values are their indices, requiring space proportional to the number of elements processed.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Same Element Twice

The Pitfall: A common mistake is checking if target - num exists without ensuring it's at a different index. This becomes problematic when exactly half of the target appears in the array.

Example of the issue:

• nums = [3, 2, 4], target = 6
• When we reach index 0 (value = 3), we calculate complement = 6 - 3 = 3
• If we had stored 3 in our dictionary first and then checked, we might incorrectly return [0, 0]

Why the given solution avoids this: The solution cleverly avoids this by checking for the complement BEFORE adding the current number to the dictionary. This ensures we never match a number with itself.

2. Overwriting Dictionary Values with Duplicate Numbers

The Pitfall: When the array contains duplicate values, storing them in the dictionary might overwrite previous indices.

Example scenario:

• nums = [3, 3], target = 6
• If we store both 3's in the dictionary, the second one overwrites the first

Why this doesn't break the solution: The algorithm finds the answer as soon as a valid pair is encountered. Since we check for complements before storing, we'll find the pair [0, 1] when processing the second 3, before any overwriting occurs. The problem guarantees exactly one solution, so we don't need to worry about finding all pairs.

3. Returning Values Instead of Indices

The Pitfall: Accidentally returning the actual numbers that sum to target instead of their indices.

Incorrect implementation:

if complement in num_to_index:
    return [complement, num]  # Wrong! Returns values

Correct implementation:

if complement in num_to_index:
    return [num_to_index[complement], index]  # Returns indices

4. Pre-populating the Dictionary

The Pitfall: Some might try to optimize by first building the complete dictionary, then searching for pairs:

# Problematic approach
num_to_index = {num: i for i, num in enumerate(nums)}
for i, num in enumerate(nums):
    complement = target - num
    if complement in num_to_index and num_to_index[complement] != i:
        return [i, num_to_index[complement]]

The issue: This approach requires extra logic to handle the same-element case and doesn't provide any performance benefit while making the code more complex.