Two Sum

Two Sum Problem

Problem Description

Given an array of integers nums and an integer target, the goal is to find two numbers within the nums array that add up to the target. The indices of these two numbers should be returned. It is assumed that there is exactly one solution, and the same element cannot be used twice.

Brute Force Solution

A straightforward approach is to iterate through the array using nested loops. For each number, check every other number to see if their sum equals the target. This is a naive solution but helps illustrate the problem.

def twoSum_bruteForce(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # No solution found

• Time Complexity: O(n^2) due to the nested loops.
• Space Complexity: O(1) as it uses constant extra space.

Optimal Solution Using a Hash Map

A more efficient solution involves using a hash map (dictionary in Python). The algorithm iterates through the array once. For each number, it checks if the complement (target - number) is already in the hash map. If it is, the indices of the current number and its complement are returned. If not, the current number and its index are added to the hash map.

def twoSum_optimal(nums, target):
    num_map = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], index]
        num_map[num] = index
    return []  # No solution found

• Time Complexity: O(n) because it iterates through the array only once.
• Space Complexity: O(n) as it potentially stores all elements of the array in the hash map.

Edge Cases

• No Solution: The problem statement guarantees that there is exactly one solution. However, in a real-world scenario, the code should handle cases where no solution exists (e.g., return an empty array or raise an exception).
• Empty Array: If the input array is empty, the algorithm should return an appropriate response (e.g., an empty array).
• Large Numbers: The code should work correctly even with large numbers, as long as they are within the integer limits of the programming language.
• Negative Numbers: The code should handle negative numbers correctly.

Summary

The optimal solution using a hash map significantly improves the time complexity from O(n^2) to O(n), making it more efficient for large input arrays. The space complexity increases to O(n), but this is a reasonable trade-off for the improved time performance.