Efficient Solutions to the Two Number Sum Problem in Python

Introduction

The "Two Number Sum" problem is a classic algorithmic challenge that tests one's ability to optimize for both time and space efficiency. This article explores various methods to find two numbers in an array that add up to a specific target sum, demonstrating how different approaches can balance performance trade-offs.

Problem Statement

Given:

• A non-empty array of distinct integers
• An integer representing a target sum

Objective:

• Find two numbers from the array that sum up to the target sum
• Return these numbers in an array (in any order)
• Return an empty array if no such pair exists

Example:

• Input:
  • array = [3, 5, -4, 8, 11, 1, -1, 6],
  • targetSum = 10
• Output: [-1, 11]

Assumptions:

• At most, one pair of numbers will sum up to the target
• The function should not return the same integer twice

Strategy and Hypothesis

Using a dictionary to store complement values will provide an efficient solution. As we iterate through the array, we can check if the complement (targetSum - currentNumber) exists in our dictionary, allowing for constant-time lookups.

Implementation

Initial Attempt: Using a Map for Quick Lookup

def twoNumberSum(array, targetSum):
    seen = {}
    for num in array:
        if targetSum - num in seen:
            return [seen[targetSum - num], num]
        else:
            seen[num] = num
    return []

This approach uses a dictionary for O(1) lookups, resulting in O(n) time complexity.

Optimizing for Space: Quadratic Time Solution

def twoNumberSum(array, targetSum):
    for i in range(len(array) - 1):
        for j in range(i + 1, len(array)):
            if array[i] + array[j] == targetSum:
                return [array[i], array[j]]
    return []

This method sacrifices time efficiency for optimal space usage.

Optimizing for Time: Hash Table Approach

def twoNumberSum(array, targetSum):
    nums = {}
    for num in array:
        potentialMatch = targetSum - num
        if potentialMatch in nums:
            return [potentialMatch, num]
        else:
            nums[num] = True
    return []

This solution achieves O(n) time complexity at the cost of O(n) space.

Optimal Space & Time: Two-pointer Technique

def twoNumberSum(array, targetSum):
    array.sort()
    left, right = 0, len(array) - 1
    while left < right:
        currentSum = array[left] + array[right]
        if currentSum == targetSum:
            return [array[left], array[right]]
        elif currentSum < targetSum:
            left += 1
        else:
            right -= 1
    return []

This approach achieves a balance between time and space efficiency.

Optimization Analysis

Space Complexity

• Quadratic Time Solution: O(1)
• Hash Table and Initial Approaches: O(n)
• Two-pointer Technique: O(1) (not counting the space used for sorting)

Time Complexity

• Quadratic Time Solution: O(n^2)
• Hash Table and Initial Approaches: O(n)
• Two-pointer Technique: O(n log n) due to sorting

Optimal Space & Time

The Two-pointer Technique offers the best overall balance:

• O(n log n) time complexity due to sorting
• O(1) additional space complexity
• Efficient for both time and space considerations

Key Takeaways

1. Hash tables can provide quick lookups at the cost of additional space
2. Brute-force methods can be space-efficient but time-consuming
3. Sorting can enable efficient algorithms like the two-pointer technique
4. Consider both time and space complexity when choosing an approach
5. The optimal solution may vary based on specific problem constraints

Conclusion

The "Two Number Sum" problem demonstrates the importance of considering multiple approaches when solving algorithmic challenges. While the two-pointer technique often provides an optimal balance of time and space efficiency, the hash table approach can be preferable when the input is not sorted and additional space usage is acceptable.

As you encounter similar problems, remember to analyze the trade-offs between time and space complexity. Practice implementing these different approaches to build your intuition for choosing the most appropriate solution based on specific problem requirements and constraints.