1. Two Sum
easyAsked at OlaFind two indices in an array whose values sum to a 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. 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^9Only 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
Try 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 each value with its index and check if the complement has already been seen in one pass.
- 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);
}
return [];
}Tradeoff:
Ola-specific tips
Ola uses this warm-up to confirm you reach for a hash map before brute force when discussing driver-rider matching lookups in a dispatch grid.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.