Two Sum — O(n) Hash Map Solution (Python, C, JavaScript)
Problem Statement
Given an array nums and integer target, return indices of the two numbers that add up to target.
Example
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] # nums[0] + nums[1] = 2 + 7 = 9
Time Complexity
O(n)
Space Complexity
O(n)
The Intuition
One-Pass Hash Map — store each number's index as we iterate. For each num, check if (target - num) is already in the map.
Solution Code
def twoSum(nums, target):
seen = {} # val -> index
for i, num in enumerate(nums):
diff = target - num
if diff in seen:
return [seen[diff], i]
seen[num] = i
return []int* twoSum(int* nums, int n, int target, int* returnSize) {
*returnSize = 2;
int* res = malloc(2 * sizeof(int));
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (nums[i] + nums[j] == target) {
res[0] = i; res[1] = j;
return res;
}
return NULL;
}function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i];
if (map.has(diff)) return [map.get(diff), i];
map.set(nums[i], i);
}
}Frequently Asked Questions
Q: Why not nested loops?
Nested loops are O(n²). For 10,000 items that is 100 million operations — too slow.
Q: Can we sort and use two pointers?
Sorting loses original indices and takes O(n log n). The hash map O(n) approach is faster.
Practice These Problems in a Real Curriculum
DoxaTech Hub's 10-month programme covers Data Structures, Algorithms, Python, C, SQL, and Full-Stack Development through 40 weeks of real, graded projects.
Get Started → More Problems