Introduction

The Two Sum problem is a classic algorithmic problem that involves finding two numbers in an array that add up to a specific target value. While a brute-force approach exists, it's often inefficient for larger arrays due to its quadratic time complexity. In this article, we'll explore an optimized solution using hash tables, which significantly improves the efficiency of solving the Two Sum problem.

Two Sum - LeetCode

Understanding the Problem

Given an array of integers and a target value, we need to find two numbers in the array such that their sum equals the target value. Each input array is guaranteed to have exactly one solution.

Naive Approach

The brute-force approach involves iterating through the array and, for each element, checking all other elements to find the complement (the target minus the current element). This approach has a time complexity of O(n^2), where n is the size of the array, due to nested loops.

Optimized Approach

To improve the efficiency of solving the Two Sum problem, we can utilize hash tables (unordered_map in C++) to store the indices of the elements we've traversed so far. This allows us to perform constant-time lookups to find the complement of each element.

Algorithm

Initialize an empty hash table to store the indices of the elements.
Iterate through the array.
For each element, calculate its complement (target minus the current element).
Check if the complement exists in the hash table.
- If it does, return the indices of the current element and its complement.
- If not, add the current element and its index to the hash table.
If no solution is found, return an empty result.

Example

Consider the array [2, 7, 11, 15] and a target value of 9.

We iterate through the array:
- For the first element (2), the complement is 9 - 2 = 7. Since 7 is not in the hash table, we add (2, 0) to the hash table.
- For the second element (7), the complement is 9 - 7 = 2. Since 2 exists in the hash table, we return (0, 1).

Intuition

The Two Sum problem involves finding two numbers in an array that add up to a specific target value. A straightforward approach could involve iterating through the array and, for each element, checking if its complement (the target minus the current element) exists in the array. However, this approach would have a time complexity of O(n^2) due to nested loops, making it inefficient for large arrays.

Approach

To optimize the solution and achieve a time complexity less than O(n^2), we can utilize a hash table (unordered_map in C++) to store the indices of the elements we've traversed so far. As we iterate through the array, we calculate the complement of each element (target minus the current element) and check if it exists in the hash table. If it does, we return the indices of the current element and its complement. If not, we add the current element and its index to the hash table. This approach allows us to find the solution in a single pass through the array, resulting in a time complexity of O(n).

Complexity

Time complexity:
The time complexity of this approach is O(n) since we traverse the array once, and each lookup operation in the hash table is on average O(1).
Space complexity:
The space complexity is also O(n) since we store at most n elements in the hash table, where n is the size of the input array.

This optimized solution efficiently solves the Two Sum problem by leveraging a hash table to store indices, enabling us to find the pair of numbers that sum up to the target value with linear time complexity.

def two_sum(nums, target):
    # Create a dictionary to store the indices of the elements
    num_indices = {}

    # Iterate through the array
    for i, num in enumerate(nums):
        # Calculate the complement
        complement = target - num

        # Check if the complement exists in the dictionary
        if complement in num_indices:
            # If it does, return the indices of the current element and its complement
            return [num_indices[complement], i]

        # Otherwise, add the current element and its index to the dictionary
        num_indices[num] = i

    # If no solution is found, return an empty list
    return []

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    // Create an unordered_map to store the indices of the elements
    std::unordered_map<int, int> num_indices;

    // Iterate through the array
    for (int i = 0; i < nums.size(); ++i) {
        // Calculate the complement
        int complement = target - nums[i];

        // Check if the complement exists in the unordered_map
        if (num_indices.find(complement) != num_indices.end()) {
            // If it does, return the indices of the current element and its complement
            return {num_indices[complement], i};
        }

        // Otherwise, add the current element and its index to the unordered_map
        num_indices[nums[i]] = i;
    }

    // If no solution is found, return an empty vector
    return {};
}

Solving the Two Sum Problem Efficiently Using Hash Tables

Table of contents