1. Two Sum
easyAsked at QuoraGiven an array of integers and a target, return indices of two numbers that add up to the target.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Each input has exactly one solution and you may not use the same element twice.
Constraints
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9Exactly one valid solution exists
Examples
Example 1
Input
nums = [2,7,11,15], target = 9Output
[0,1]Example 2
Input
nums = [3,2,4], target = 6Output
[1,2]Approaches
1. Brute force
Check every pair of indices.
- Time
- O(n^2)
- Space
- O(1)
for (let i = 0; i < nums.length; i++) {
for (let j = i+1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}Tradeoff:
2. Hash map
Store complement -> index as you iterate. One pass.
- Time
- O(n)
- Space
- O(n)
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (map.has(need)) return [map.get(need), i];
map.set(nums[i], i);
}
return [];
}Tradeoff:
Quora-specific tips
Quora opens with Two Sum to watch how cleanly you reach for a hash lookup — the same primitive powers their question-dedup and answer-ranking inverted indexes.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.