You are given an array of integers nums and an integer target.

Problem:

Write a function twoSum that finds two distinct numbers in the nums array that add up to the target. The function should return an array containing the indices of the two numbers. If no such pair exists, return an empty array.

Example:

nums = [2, 7, 11, 15]
target = 9

twoSum(nums, target) == [0, 1]  // Because nums[0] + nums[1] == 2 + 7 == 9

nums = [3, 2, 4]
target = 6

twoSum(nums, target) == [1, 2]  // Because nums[1] + nums[2] == 2 + 4 == 6

nums = [3, 3]
target = 6

twoSum(nums, target) == [0, 1]  // Because nums[0] + nums[1] == 3 + 3 == 6

Constraints:

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

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

Two Sum Problem

Problem

You are given an array of integers nums and an integer target. Write a function twoSum that finds two distinct numbers in the nums array that add up to the target. The function should return an array containing the indices of the two numbers. If no such pair exists, return an empty array.

Examples

nums = [2, 7, 11, 15]
target = 9

twoSum(nums, target) == [0, 1]  // Because nums[0] + nums[1] == 2 + 7 == 9

nums = [3, 2, 4]
target = 6

twoSum(nums, target) == [1, 2]  // Because nums[1] + nums[2] == 2 + 4 == 6

nums = [3, 3]
target = 6

twoSum(nums, target) == [0, 1]  // Because nums[0] + nums[1] == 3 + 3 == 6

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 checking every possible pair of numbers in the array to see if they add up to the target. This approach has a time complexity of O(n^2).

def twoSum_brute_force(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Optimal Solution

A more efficient solution involves using a hash map (dictionary in Python) to store each number and its index. We iterate through the array, and for each number, we check if the complement (target - number) exists in the hash map. If it does, we have found our pair. This approach has a time complexity of O(n).

def twoSum(nums: list[int], target: int) -> list[int]:
    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 []

Example Usage

nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))  # Output: [0, 1]

nums = [3, 2, 4]
target = 6
print(twoSum(nums, target))  # Output: [1, 2]

nums = [3, 3]
target = 6
print(twoSum(nums, target))  # Output: [0, 1]

nums = [1, 4, 7, 2, 9]
target = 11
print(twoSum(nums, target))  # Output: [2, 3]

nums = [1, 5, 9]
target = 10
print(twoSum(nums, target)) # Output: [0, 2]

nums = [3, 5, -4, 8, 11, 1, -1, 6] # complex list
target = 10
print(twoSum(nums, target)) # Output: [0, 4]

Time Complexity Analysis

The time complexity of the optimal solution is O(n), where n is the length of the input array nums. This is because we iterate through the array once to build the hash map and then iterate through it again (in the worst case) to find the complement. The hash map allows us to perform lookups in O(1) average time.

In the brute force solution, we have nested for loops which results in O(n^2) time complexity.

Space Complexity Analysis

The space complexity of the optimal solution is O(n), where n is the length of the input array nums. This is because, in the worst case, we might store all the numbers in the hash map.

The brute force solution has O(1) space complexity because it doesn't use any extra space besides a few variables.

Edge Cases

• Empty Array: If the input array is empty or has fewer than two elements, the function should return an empty array, as there cannot be two distinct numbers that add up to the target.
• No Solution: If no pair of numbers in the array adds up to the target, the function should return an empty array.
• Duplicate Numbers: If the array contains duplicate numbers, the function should still find the correct pair. The hash map approach handles this correctly.
• Large Numbers: The numbers in the array and the target value can be large (within the specified constraints). The solution should handle these large numbers without overflow issues.
• Negative Numbers: The array can contain negative numbers. The solution should handle negative numbers correctly.
• Target Exists Multiple Times: If the same target can be achieved by multiple pairs, then only one of them is returned since the problem statement mentions that only one valid answer exists.

Follow-up

The provided hash map solution achieves O(n) time complexity, which is less than O(n^2). Therefore, it satisfies the follow-up question.