Solving tips
- At index i you know the exact value needed: complement = target - nums[i]; the slow part is searching for it, which a hash map makes O(1).
- One pass: for each element check if its complement is already in a value->index dict, else insert the current element; O(n) time, O(n) space.
- Check for the complement BEFORE inserting the current element — this guarantees distinct indices and handles duplicates like [3,3].
- Pitfall: the array is unsorted and values can be negative, so a sort+two-pointer approach must carry original indices and there are no sign-based shortcuts.
Problem
You are given an array of integers nums and an integer target. Find the two different positions in the array whose values add up exactly to target, and return those two indices (in any order).
You may assume every input has exactly one valid answer, and you cannot use the element at the same index twice (though two equal values at different indices are fine).
Examples
nums = [2, 7, 11, 15], target = 9 → [0, 1] — because 2 + 7 = 9.nums = [3, 2, 4], target = 6 → [1, 2] — 2 + 4 = 6; note you may not use index 0 twice even though 3 + 3 = 6.nums = [3, 3], target = 6 → [0, 1] — equal values at two different indices are allowed.
Constraints
2 <= nums.length <= 10^4-10^9 <= nums[i], target <= 10^9- Exactly one valid answer exists.
The array is not sorted, and with up to 10^4 elements a quadratic scan is already ~10^8 pair checks — the intended solution is linear.
Think about it first
Hint 1
Standing at index `i`, you already know exactly which value would complete the pair. What is it?
Hint 2
The slow part of the naive solution is *searching* for that complementary value. What data structure answers "have I seen value v, and where?" in O(1)?
Hint 3
Walk the array once, keeping a dict from value → index of the elements you've already passed. At each element, look up `target - nums[i]` in the dict *before* inserting the current element — that also prevents matching an element with itself.
TL;DR
One-pass hash map — O(n) time, O(n) space.
Approach 1 — Brute force
Try every pair of indices and check whether the values sum to the target.
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return [] # unreachable: exactly one answer is guaranteed
Complexity: O(n²) time, O(1) space.
With n up to 10^4 that is ~5·10^7 pair checks — acceptable in C, sluggish in Python, and clearly not what the problem is testing.
Approach 2 — Sort + two pointers
The insight: in a sorted array, you can find a pair with a given sum in linear time by walking two pointers inward — too small a sum means advance the left pointer, too large means retreat the right one. The catch here is that the answer needs original indices, so we must sort (value, index) pairs, not bare values.
Two pointers is the classical technique of scanning a sorted sequence from both ends and moving one end based on a monotone comparison.
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
order = sorted(range(len(nums)), key=lambda i: nums[i])
lo, hi = 0, len(nums) - 1
while lo < hi:
i, j = order[lo], order[hi]
s = nums[i] + nums[j]
if s == target:
return [i, j]
if s < target:
lo += 1
else:
hi -= 1
return []
Walkthrough on nums = [3, 2, 4], target = 6:
- Indices sorted by value:
order = [1, 0, 2] (values 2, 3, 4).
lo=0, hi=2: values 2 + 4 = 6 — match. Return the original indices [1, 2].
Complexity: O(n log n) time for the sort, O(n) space for the index array.
Approach 3 — One-pass hash map
The insight: at index i you know the exact value you need — target - nums[i]. A hash map from value → index lets you ask “have I already walked past that value?” in O(1). Checking before inserting the current element guarantees the two indices are distinct.
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen: dict[int, int] = {} # value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
Walkthrough on nums = [3, 2, 4], target = 6:
i=0, num=3: complement 3 not in seen → store {3: 0}.i=1, num=2: complement 4 not in seen → store {3: 0, 2: 1}.i=2, num=4: complement 2 is in seen at index 1 → return [1, 2].
Complexity: O(n) time — one pass, O(1) expected work per element; O(n) space for the map.
Common pitfalls
- Inserting the current element into the map before checking for its complement — with
target = 6 and nums = [3, 2, 4] you would wrongly pair index 0 with itself.
- Building a full value → index map first and then failing the duplicate case (
[3, 3], target 6): the second 3 overwrites the first, so a naive two-pass lookup returns the same index twice unless you check seen[complement] != i.
- Sorting and returning the sorted positions instead of the original indices.
- Assuming values are positive — they can be negative, so “complement is negative, skip” style shortcuts are wrong.
Pattern takeaway
When a scan needs to answer “have I already seen the thing that completes what I’m holding?”, store what you’ve passed in a hash map keyed by the property you’ll look up. Trading O(n) memory to make membership tests O(1) is the core move of the Arrays & Hashing pattern.