How would you leverage the use of a hash table to tackle the two sum problem in O(n) time complexity?

Question Analysis

The "Two Sum" problem is a classic algorithmic challenge where you are given an array of integers and a target sum. The goal is to determine if there are two distinct numbers in the array that add up to the target sum and to return the indices of these two numbers. The problem requires a solution with a time complexity of O(n), which suggests that a single-pass solution over the array is ideal. A hash table (or dictionary/map) is particularly useful here because it provides average O(1) time complexity for insertions and lookups, which can help achieve the desired overall time complexity.

Answer

To solve the Two Sum problem using a hash table in O(n) time, follow these steps:

1. Initialize a Hash Table: Create an empty hash table (or dictionary) to store numbers from the array and their corresponding indices.

2. Iterate through the Array: Loop through each element in the array using its index.

3. Calculate the Complement: For each element, calculate the complement by subtracting the current element from the target sum. This complement is the number needed to reach the target sum when added to the current element.

4. Check the Hash Table:

   • If the complement is already in the hash table, it means we have found the two numbers that add up to the target. Retrieve the index of the complement from the hash table and return both indices.
   • If the complement is not in the hash table, add the current element and its index to the hash table for future reference.

5. Return the Indices: Once the correct pair is found, return their indices.

Here's the pseudocode for this approach:

def two_sum(nums, target):
    # Initialize the hash table
    hash_table = {}
    
    # Iterate over the array
    for index, number in enumerate(nums):
        # Calculate the complement
        complement = target - number
        
        # Check if the complement is in the hash table
        if complement in hash_table:
            # Return the indices of the two numbers
            return [hash_table[complement], index]
        
        # Add the current number and its index to the hash table
        hash_table[number] = index
    
    # If no solution is found, return an empty array or raise an error
    return []

# Example usage:
# nums = [2, 7, 11, 15], target = 9
# Output: [0, 1] because nums[0] + nums[1] = 9

This solution efficiently finds the indices of the two numbers summing to the target in a single pass through the array, achieving the desired O(n) time complexity.