Two Sum
Given an array of integers nums and an integer target, write a function twoSum that returns the indices of the two numbers such that they add up to the target. You may assume that each input will have exactly one solution, and you may not use the same element twice. If no such pair exists, return an empty array. If there are multiple pairs of indices that sum to the target, return the indices of the pair where the numbers appear first in the array.
Examples
Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Input: nums = [3, 2, 4], target = 6 Output: [1, 2]
The brute force approach has a time complexity of O(n^2). We can do better.
Consider using a hash map to store the elements of the array along with their indices as you iterate through the array.
Implement the solution efficiently in terms of both time and space. Aim for an O(n) time complexity.
Solution 1: Hash map approach
Our solution processes the input array by iterating through it while maintaining a hash map of previously seen elements and their indices. For each element, it calculates the complement (i.e., target - nums[i]) and checks if this complement is already present in the hash map. If the complement is found, it means we have identified a pair of indices that sum up to the target, and we return these indices. If no such pair is found by the end of the iteration, we return an empty array.
The solution uses a hash map (or unordered map) to achieve efficient lookups and insertions. This approach ensures that each element is processed only once, making it both readable and performant.
from typing import List
def two_sum(nums: List[int], target: int) -> List[int]:
num_to_index = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], i]
num_to_index[num] = i
return []Time Complexity: The solution has a time complexity of O(n), where n is the number of elements in the array. This is because we iterate through the array once, performing constant-time operations (hash map lookups and insertions) for each element.
Space Complexity: The solution uses O(n) space for the hash map that stores the indices of the elements. In the worst case, if all elements are unique, the hash map will contain n entries.
Solution 2: Two-pointer approach
In this approach, we sort the input array first and then use a two-pointer technique to find the pair of numbers that sum up to the target. The idea is to place one pointer at the beginning (left) and another at the end (right) of the sorted array. We compute the sum of the elements at these two pointers.
-
If the sum equals the target, we need to find the pair with the lowest index right number. We iterate from the current
rightpointer to find the smallest index where the number is equal to the currentrightvalue and ensure thatright != left. This step ensures that if there are multiple pairs summing to the target, we return the indices of the pair where the numbers appear first in the array. -
If the sum is less than the target, we move the left pointer to the right to increase the sum.
-
If the sum is greater than the target, we move the right pointer to the left to decrease the sum.
Sorting the array allows us to effectively narrow down our search using the two-pointer technique, and iterating to find the lowest index right number ensures we return the correct pair according to the problem's requirements.
from typing import List
def two_sum(nums: List[int], target: int) -> List[int]:
nums_with_index = [(num, i) for i, num in enumerate(nums)]
nums_with_index.sort() # Sort by the values
left, right = 0, len(nums_with_index) - 1
while left < right:
current_sum = nums_with_index[left][0] + nums_with_index[right][0]
if current_sum == target:
# Check for duplicates on the right side but ensure we don't decrement right too far
while right > left + 1 and nums_with_index[right][0] == nums_with_index[right - 1][0]:
right -= 1
# Return the original indices, sorted to match expected output order
return sorted([nums_with_index[left][1], nums_with_index[right][1]])
elif current_sum < target:
left += 1
else:
right -= 1
return []Time Complexity: The time complexity of this solution is O(n log n) due to the sorting step. After sorting, the two-pointer traversal takes O(n) time, but sorting dominates the complexity.
Space Complexity: The space complexity is O(n) to store the original indices along with the elements of the array, which is necessary to return the correct indices after sorting.
In what situation would we go for Solution 2 (two-pointer approach) over Solution 1?
Check out our lesson on the two-pointer approach to learn more about it and its applications!
Arrays.sort(inputarray) sliding window with a size of 2. Check for the sum in the sliding window. subtract the start when window moves