~/problems / Arrays & hashing / Hash maps and counting

Two Sum

easy ~15 min

Write two_sum(nums, target) that returns [i, j] with i < j such that nums[i] + nums[j] == target, or None if no such pair exists.

  • If several pairs work, any one is accepted.
  • You may not use the same index twice (but two different indexes may hold equal values).
  • 1 <= len(nums) <= 2 * 10^5; values are in [-10^9, 10^9] and target is in [-2 * 10^9, 2 * 10^9].
  • Checking every pair is O(n²), too slow at this size. Aim for O(n).
two_sum([4, 11, -3, 8], 5)   # [2, 3]   (-3 + 8)
two_sum([6, 6], 12)          # [0, 1]
two_sum([5], 10)             # None
Show hint

for each x you scan, the only partner that works is target - x. Can you check in O(1) whether you've already seen it, and where?

Topic: Hash maps and counting. Counter/defaultdict, complement lookups, prefix-sum + hash map.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc