AlgoBreath

Two Sum

The "Two Sum" problem is a classic algorithmic challenge that involves finding two numbers in an array that add up to a specific target sum. Let's break down the problem and its solution using fundamental principles of computer science and mathematics.

Problem Statement:

  1. Input: An array (or list) of numbers and a target sum.
  2. Goal: Find two different elements in the array whose sum equals the target sum.

Key Points to Consider:

  • The solution can be either the indices of the two numbers or the numbers themselves, depending on the problem statement.
  • The array may have multiple pairs that add up to the target sum, but we are usually interested in finding just one valid pair.
  • The array might not have any pair that adds up to the target sum, in which case we need to report no solution.

Solution Approaches:

  1. Brute Force Method:

    • Idea: Check every possible pair in the array.
    • Implementation: Use two nested loops; the outer loop iterates through each element, and the inner loop checks all subsequent elements to find a pair that adds up to the target sum.
    • Time Complexity: O(n²), where n is the number of elements in the array. This is because for each element, we are checking all other elements.
    • Space Complexity: O(1), as no extra space is required apart from the input array.

  2. Using a Hash Table:

    • Idea: Use a hash table (dictionary in Python) to store the difference between the target sum and the current element. If at any point, a number in the array matches a value in the hash table, we have found a pair.
    • Implementation: Iterate through the array, for each element, check if it is present in the hash table. If it is not, insert the difference of the target sum and the current element into the hash table. If it is present, we have found our pair.
    • Time Complexity: O(n), since we traverse the list containing n elements only once. Each look-up in the table costs only O(1) time.
    • Space Complexity: O(n), in the worst case, the extra space required (for the hash table) depends on the number of elements in the array.

Example Implementation in Python (Using Hash Table):

Here's an example implementation of the Two Sum problem using a hash table in Python:

def two_sum(nums, target):
    """
    Finds two numbers such that they add up to a specific target.

    Args:
    nums (List[int]): The list of numbers.
    target (int): The target sum.

    Returns:
    List[int]: A list containing the indices of the two numbers that add up to the target.
    """
    num_map = {}  # Initialize an empty hash table (dictionary in Python)
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]  # Found the pair
        num_map[num] = i  # Store the index of the current number
    return []  # Return an empty list if no pair is found

# Example usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1], since nums[0] + nums[1] = 2 + 7 = 9

This code is comprehensive because it:

  • Initializes a hash table to store indices of elements.
  • Iterates over each element in the array.
  • For each element, calculates the complement (what value, when added to this element, equals the target sum).
  • Checks if the complement is already in the hash table. If yes, returns the indices of the complement and the current element.
  • If not, stores the current element's index in the hash table.
  • Returns an empty list if no pair is found, indicating no solution.

Next