Two Sum
An easy Arrays problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Arrays
- Sheets
- 3
- Core for
- 25 roles
- Platform
- LeetCode
The problem
Given an array of integers and a target sum, locate the indices of the two distinct elements that add up to the target value.
Example 1
- Input
- nums = [2,7,11,15], target = 9
- Output
- [0,1]
- Why
- nums[0] + nums[1] equals 2 + 7 = 9, so returning indices [0, 1] satisfies the target.
Example 2
- Input
- nums = [3,2,4], target = 6
- Output
- [1,2]
- Why
- nums[1] + nums[2] equals 2 + 4 = 6, which adds up to the required target.
Example 3
- Input
- nums = [3,3], target = 6
- Output
- [0,1]
- Why
- The two distinct indices 0 and 1 hold matching values that sum up to 6.
Constraints
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
How to think about it
Updated 2026-09-09Looking for two numbers that sum to a target means that every examined value fixes the exact counterpart it needs: target - x. Instead of scanning backwards to check whether that counterpart appeared, a hash table turns each past element into an instant lookup. One forward march checks for the needed complement and registers the current value for future elements.
Approaches, worst first
Exhaustive pair enumeration
time O(n^2) · space O(1)
Test every pair of indices (i, j) with i < j using nested loops and compare their sum to the target. Guaranteed to locate the pair if one exists, but recalculates sums without retaining any memory of previously seen numbers.
Sort and two-pointer inward sweep
time O(n log n) · space O(n)
Preserve the original indices alongside values, sort the list ascending, and place pointers at the two ends. Summing the boundaries directs the search inward: a small sum advances left, while a large sum decrements right. Beats quadratic scanning but incurs the cost of an array sort.
One-pass hash map complement lookupWrite this one
time O(n) · space O(n)
Iterate through the array while maintaining a map from element value to its index. For each number, query whether (target - num) already exists in the table. If found, return the stored index paired with the current index; otherwise insert the current number and proceed.
Where people lose marks · 3
- Returning the same index twice when target equals 2 * nums[i] because the lookup finds the element currently being evaluated.
- Populating the entire hash map in a preliminary pass before checking complements, which causes duplicates to overwrite earlier indices and miss identical pairs.
- Sorting in place without preserving original array indices, which returns positions in the sorted permutation rather than indices in the original input.
Full solution
One-pass hash map complement lookup: O(n) time, checks and inserts in the same loop so it never returns the same index twice.
Python
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
JavaScript
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
return [];
}
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
What each operation costs
| Operation | Time |
|---|---|
| look up element by index | O(1) |
| insert or delete at the start | O(n) |
| search an unsorted collection for a value | O(n) |
What usually goes wrong with Arrays
- Reading past the final index by checking index less than or equal to length instead of strictly less than length, triggering index out of bounds exceptions.
- Modifying length or removing elements during a forward iteration loop, which causes remaining items to shift left and skip validation on the next neighbor.
- Assuming dynamic resizing is costless inside nested loops, causing repeated memory reallocation copies when appending unknown quantities of items.
Which roles need this problem
Arrays is a core topic for these 25 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 3 more roles, including Database Engineer, Bioinformatics Engineer, Networking Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Arrays problems
Problem set and role mapping as of .