Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

• Input: nums = [2,7,11,15], target = 9
• Output: [0,1]
• Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

• Input: nums = [3,2,4], target = 6
• Output: [1,2]

Example 3:

• Input: nums = [3,3], target = 6
• Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Two Sum

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

• Input: nums = [2,7,11,15], target = 9
• Output: [0,1]
• Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

• Input: nums = [3,2,4], target = 6
• Output: [1,2]

Example 3:

• Input: nums = [3,3], target = 6
• Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Brute Force Solution

The brute force solution involves iterating through each element in the nums array and checking the sum of every other element to see if it equals the target. If it does, return the indices of the two elements.

def twoSum_brute_force(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 []

Optimal Solution

The optimal solution uses a hash map to store each number and its index. Iterate through the array, and for each number, check if the complement (target - number) is already in the hash map. If it is, return the current index and the index of the complement. If not, add the number and its index to the hash map.

def twoSum(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 []

Big(O) Time Complexity Analysis

Brute Force

The brute force solution has a time complexity of O(n^2) because it involves nested loops. The outer loop iterates n times, and the inner loop iterates n-i times, resulting in roughly n^2 comparisons in the worst case.

Optimal Solution

The optimal solution has a time complexity of O(n) because it involves a single loop that iterates through the array once. Hash map lookups take O(1) on average, so checking for the complement in the hash map is effectively constant time for each element in the array.

Big(O) Space Complexity Analysis

Brute Force

The brute force solution has a space complexity of O(1) because it doesn't use any additional data structures that scale with the input size. It only uses a fixed number of variables to store indices and perform comparisons.

Optimal Solution

The optimal solution has a space complexity of O(n) because, in the worst-case scenario, we may need to store every element of the nums array in the hash map. The hash map num_map grows linearly with the input size.

Edge Cases

1. Empty Array: If the input array nums is empty, the function should return an empty list because there are no elements to sum up to the target.
2. No Solution: If no two numbers in the array sum up to the target, the function should return an empty list.
3. Duplicate Numbers: The problem states that each input has exactly one solution, and you may not use the same element twice. The hash map approach handles duplicate numbers correctly because it stores the first occurrence of each number.
4. Large Numbers: The constraints specify that numbers can be as large as 10^9. Python can handle integers of this magnitude without issues. No special handling is needed for large numbers.

# Example usage:
nums1 = [2, 7, 11, 15]
target1 = 9
print(f"Input: nums = {nums1}, target = {target1}")
print(f"Output: {twoSum(nums1, target1)}")

nums2 = [3, 2, 4]
target2 = 6
print(f"Input: nums = {nums2}, target = {target2}")
print(f"Output: {twoSum(nums2, target2)}")

nums3 = [3, 3]
target3 = 6
print(f"Input: nums = {nums3}, target = {target3}")
print(f"Output: {twoSum(nums3, target3)}")

nums4 = []
target4 = 6
print(f"Input: nums = {nums4}, target = {target4}")
print(f"Output: {twoSum(nums4, target4)}")

nums5 = [1,2,3]
target5 = 10
print(f"Input: nums = {nums5}, target = {target5}")
print(f"Output: {twoSum(nums5, target5)}")