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 common coding interview question where you are given an array of integers and a target sum. The task is to find two distinct numbers in the array that add up to the target sum and return their indices. The challenge is to achieve this in O(n) time complexity, where n is the number of elements in the array.

To solve this problem efficiently, we can use a hash table (or hash map) to store elements and their indices as we iterate through the array. The hash table allows for average O(1) time complexity for both insertion and lookup operations, making it a suitable data structure to achieve the desired overall time complexity of O(n).

Answer

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

1. Initialize a Hash Table: Create an empty hash table (dictionary in Python) to store each number in the array and its corresponding index.

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

3. Check for Complement: For each number, calculate its complement with respect to the target sum (complement = target - current_number). Check if this complement exists in the hash table:

   • If the complement is found, it means the current number and its complement add up to the target sum. You can then return the indices of these two numbers.
   • If the complement is not found, store the current number and its index in the hash table for future reference.

4. Return the Result: Once a valid pair is found, return the indices of the two numbers.

Here is a concise implementation in Python:

def two_sum(nums, target):
    num_to_index = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], index]
        num_to_index[num] = index
    return []

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

Key Points:

• Efficiency: The solution runs in O(n) time complexity as each element is processed at most twice (once when added and once when checked for a complement).
• Space Complexity: The space complexity is O(n) due to the storage required for the hash table.
• Correctness: The algorithm ensures that the pair of indices returned corresponds to numbers that sum up to the target, and it does so by maintaining a record of previously seen elements using the hash table.