Developers

Two Sum

EasyHashing and countingGrade BAlso known as LeetCode 1

You get a list of integers called nums and a single integer called target.

Return the positions of two different entries whose values add up to target. Each input has exactly one valid pair. You may not use the same position twice, but two positions can hold equal values.

The two positions can be returned in either order.

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]
The first 3 cannot pair with itself.
Input nums = [3, 3], target = 6
Output [0, 1]
Equal values are fine when the positions differ.

Constraints

  • 2 <= nums.length <= 10,000
  • -1,000,000,000 <= nums[i] <= 1,000,000,000
  • -1,000,000,000 <= target <= 1,000,000,000
  • Exactly one valid pair exists.

Stuck? Take one hint at a time

Common mistakes
  • Storing the current number before looking up its partner, which lets a position pair with itself.
  • Returning values instead of positions.
  • Sorting the list first and losing the original positions.
  • Forgetting that two equal values are a valid pair when they sit at different positions.
  • Using a 32-bit int for sums when the bounds allow larger totals. Here the totals fit, but only just.
Questions an interviewer may ask next
  • The list is already sorted. Can you solve it in O(1) extra space? (Two pointers from both ends.)
  • There may be many valid pairs. Return all of them without repeats.
  • The numbers arrive one at a time as a stream. Design a class with add(value) and find(target).
  • Return a triple instead of a pair. How does the cost change?
  • The list does not fit in memory. What do you change?

How often this is reported

Commonly reported across 18 of 25 tracked companies
18/25

Grade B: Reported in more than one source. This reflects what candidates report, not a guarantee of what any company will ask.