1. Two Sum
easyAsked at AutodeskFind two indices whose values add up to a given target.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an array of integers and a target value, return indices of the two numbers such that they add up to target. You may assume 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 answer 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 with nested loops.
- 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 complements in a map so each lookup is O(1). One pass solves the problem.
- Time
- O(n)
- Space
- O(n)
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
}Tradeoff:
Autodesk-specific tips
At Autodesk this warms up index-pair reasoning that appears in mesh edge lookups and BVH overlap pairs.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.