Two Sum - Solution
Solutions and explanations
Video Explanation
In this approach, we check every possible pair of elements to see if their sum equals the target.
As soon as we find a pair that satisfies the condition, we return their indices.
class Solution:
def twoSum(self, 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 indices of the matching pair
return [] # no matching pair found
Complexity Analysis
Here, n is the input size.
- Time Complexity:
O(n²)– In the worst case, we may need to check every possible pair of elements. - Space Complexity:
O(1)
In this approach, we use a hashmap to store each number seen so far along with its index.
For each number, we check if its complement (target - number) exists in the map or not:
- If the complement is already present, we return the indices of the current number and its complement as result
- If not, we continue scanning and add the current number and its index to the hashmap.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {} # num : idx
for idx, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], idx]
seen[num] = idx
return []
Complexity Analysis
Here, n is the input size.
- Time Complexity:
O(n)– Each element is traversed atmost once. - Space Complexity:
O(n)– In the worst case, the hashmap may need to store up tonelements.