LeetCode Solutions Blog

Two Sum

Number: 1

Difficulty: Easy

Paid? No

Problem Description

Given an array of integers and an integer target, return indices of the two numbers such that they add up to the target. Each input has exactly one solution and the same element cannot be used twice. The answer can be returned in any order.

Key Insights

Use a hash table to store the elements and their indices for fast lookup.
For each element, calculate its complement: target minus the current element.
Check if the complement exists in the hash table.
If found, return the indices of the current element and its complement.
This approach only requires a single pass through the array.

Space and Time Complexity

Time Complexity: O(n) - We traverse the list only once. Space Complexity: O(n) - In the worst-case, we store all elements in the hash table.

Solution

We use a hash table (dictionary) to map each array element to its index as we iterate. For each number, we compute the complement (target - number) and check if it already exists in our hash table. If the complement is found, we return the indices. This one-pass solution ensures linear time complexity and avoids the need for nested loops.

Code Solutions

def two_sum(nums, target):
    # Create a dictionary to store the number and its index
    num_to_index = {}
    # Iterate over the list with index
    for index, num in enumerate(nums):
        # Calculate the complement needed to reach the target
        complement = target - num
        # Check if the complement is in the dictionary
        if complement in num_to_index:
            # Return the index of the complement and the current index
            return [num_to_index[complement], index]
        # Store the number with its index
        num_to_index[num] = index
    # Since the problem guarantees one solution, we don't need a return statement here.
    
# Example usage:
# print(two_sum([2, 7, 11, 15], 9))  # Output: [0, 1]