Problem statement
You are given:
• An array of integers nums
• An integer target
You must find the indices of the two numbers in nums that add up
exactly to target.
• There will always be exactly one valid answer.
• You cannot use the same element twice.
• Return the indices in any order.
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
Naive solution (O(n²))
We can check every possible pair:
def twoSum(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]
• Time complexity: O(n^2)
• Space complexity: O(1)
This works for small arrays but is slow for large inputs.
Optimized solution (O(n)) using a hash map
We can store numbers we’ve already seen in a dictionary for instant
lookups.
def twoSum(nums, target):
seen = {} # number → index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
How it works:
1. For each number, compute complement = target - num×
2. If the complement has already been seen, return its index +
current index.
3. Otherwise, store the current number and index in seen.
Example walkthrough:
• nums = [2, 7, 11, 15], target = 9
• i=0 → num=2 → complement=7 → not seen yet → store {2:0}
• i=1 → num=7 → complement=2 → found in seen! return [0, 1]
Final Answer:
• Time complexity: O(n)
• Space complexity: O(n)
• Works efficiently even for large arrays.
