1. Two Sum
easyGiven an array of integers and a target sum, return the indices of the two numbers that add up to the target. Classic warm-up problem testing hash-map intuition and the space-for-time tradeoff.
By Alex Chen, 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 that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Constraints
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9Only one valid answer exists.
Examples
Example 1
nums = [2,7,11,15], target = 9[0,1]Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2
nums = [3,2,4], target = 6[1,2]Example 3
nums = [3,3], target = 6[0,1]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
The brute-force approach tries every pair of indices. What does that cost you?
Hint 2
If you could ask 'is the value I need already somewhere in this array?' in constant time, the problem becomes a single pass. What data structure gives you that?
Hint 3
Walk the array once. For each num at index i, compute complement = target - num. If complement is already in your hash map, return [map[complement], i]. Otherwise store num -> i and continue.
Solution approach
Reveal approach
Use a hash map that stores each value's index as you scan the array. For each new number, compute its complement (target minus the current value) and check if that complement is already in the map. If yes, return the complement's stored index and the current index. Otherwise, insert the current value and index into the map and continue. The one-pass version handles all cases because by the time you'd want to pair value X with value Y, you've already inserted whichever appeared first.
Complexity
- Time
- O(n)
- Space
- O(n)
Related patterns
- hash-map
- two-pointers
Related problems
- 15. 3Sum
- 167. Two Sum II - Input Array Is Sorted
- 18. 4Sum
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
- Apple
Practice these live with InterviewChamp.AI
Drill Two Sum and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →