Two Sum

Difficulty: Easy

Problem

You get an integer array 'nums' and an integer 'target'. Find the two entries whose values add up to the target and return their indices. Each input is guaranteed to have exactly one answer, and the same element cannot be used twice.

Example

Input: nums = [2, 11, 7, 15], target = 9
Output: [0, 2]
Explanation: Because nums[0] + nums[2] = 2 + 7 = 9, we return [0, 2].

Brute-force approach

Check every possible pair of numbers to see if they add up to the target.

Steps

  1. Pick the first number
  2. Compare it with every other number
  3. Check if their sum equals target
  4. Repeat for all numbers

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Very slow for large arrays
  • n² comparisons needed
  • Inefficient for repeated lookups

Optimal approach

Key insight: For each number, we need target - number. If we've seen it before, we found our pair!

Use a hash map to remember numbers we've seen, so we can find complements in O(1) time.

Steps

  1. Look at current number
  2. Calculate complement (target - current)
  3. Check if complement is in hash map
  4. If not, store current number and its index

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function twoSum(nums, target):
    create empty hashmap
    
    for each index i, num in nums:
        complement = target - num
        
        if complement exists in hashmap:
            return [hashmap[complement], i]
        
        store num -> i in hashmap
    
    return no solution

Hints

  • Think about what you need to find for each number (target - current = complement)
  • How can you check if you've seen a number before in O(1) time?
  • What should you store in the hash map? (number -> its index)

Complexity questions

What is the time complexity of checking every pair?

O(n²). Two nested loops: outer runs n times, inner runs n times = O(n²)

Space complexity of brute force?

O(1). Only using a few variables, no additional data structures.

Time complexity with hash map?

O(n). Single pass through array with O(1) hash lookups = O(n)

Space complexity with hash map?

O(n). Worst case: store all n elements in the hash map.

Check your understanding of Two Sum

What is the goal of the Two Sum problem?

Find two numbers that add up to a target value. The Two Sum problem asks us to find exactly two numbers in the array whose sum equals the given target value.

Given nums = [3, 8, 2, 15, 4, 7, 12] and target = 9, what should be returned?

[2, 5] - the indices of the numbers. We return the INDICES (positions) of the two numbers, not the numbers themselves. The value 2 is at index 2, and value 7 is at index 5. Since 2 + 7 = 9, we return [2, 5].

Can we use the same element twice to reach the target?

No, we must use two different elements. The problem requires finding TWO DIFFERENT elements. Even if doubling one number gives us the target, we cannot use the same element twice.

Related problems

Keep practising