mafeshsho8lmafeshsho8l
Get Started
All coding questions

Two Sum

easy
Blind 75NeetCode 150arrayshashing

Problem

Given a list of integers and a target value, find the two distinct positions whose values add up to the target. Return those two positions. Assume exactly one such pair exists.

Examples

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
nums[0] + nums[1] = 2 + 7 = 9.
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
nums[1] + nums[2] = 2 + 4 = 6.

Constraints

  • • 2 <= nums.length <= 10^4
  • • -10^9 <= nums[i] <= 10^9
  • • Exactly one valid pair exists
Hints(tap to reveal)
  • 1. A brute-force double loop is O(n^2).
  • 2. What if you remembered every value you've already seen, with its index?
Optimal approach(spoiler)
  1. Scan the array once, keeping a hash map from value to its index.
  2. For each value v, compute the complement target - v.
  3. If the complement is already in the map, return the two indices.
  4. Otherwise store v with its index and continue.
  5. Runs in O(n) time and O(n) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor