Two Sum

Problem: Two Sum

1. Clarify the problem

The "Two Sum" problem typically asks you to find two numbers in an array that add up to a given target sum.

2. Analyze the problem

Given an array of integers and a target sum, we need to find two numbers in the array that add up to the target sum. The solution should return the indices of the two numbers.

3. Design an algorithm

One approach to solving this problem is by using a hash map. We can iterate through the array and for each element, check if the difference between the target sum and the current element exists in the hash map. If it does, we have found the pair that adds up to the target sum. If it doesn't, we add the current element to the hash map for future lookups.

4. Explain the approach

We will iterate through the array and for each element, calculate the difference between the target sum and the current element. We will check if this difference exists in the hash map. If it does, we will return the indices of the current element and the difference. If it doesn't, we will add the current element and its index to the hash map.

5. Write clean and readable code

def twoSum(nums, target):
    num_map = {}
    for index, num in enumerate(nums):
        diff = target - num
        if diff in num_map:
            return [num_map[diff], index]
        num_map[num] = index
    return []

def main():
    test_cases = [
        ([2, 7, 11, 15], 9),  # Expected output: [0, 1]
        ([3, 2, 4], 6),  # Expected output: [1, 2]
        ([3, 3], 6),  # Expected output: [0, 1]
        ([1, 2, 3, 4, 5], 10),  # Expected output: []
    ]
    
    for nums, target in test_cases:
        result = twoSum(nums, target)
        print(f"Array: {nums}, Target: {target}  Result: {result}")


if __name__ == '__main__':
    main()

6. Test the code

We will test the code with different test cases, including cases with valid solutions and cases with no valid solutions.

7. Optimize if necessary

The given solution has a time complexity of O(n) because we iterate through the array once. This is already an optimal solution for the "Two Sum" problem.

8. Handle error cases

The code currently assumes that the input array will always contain at least two elements. If the input array is empty or has only one element, the code will return an empty list. We can add a check at the beginning of the function to handle these cases explicitly.

9. Discuss complexity analysis

The time complexity of the solution is O(n) since we iterate through the array once. The space complexity is O(n) as well, considering the worst-case scenario where all elements are stored in the hash map.