LeetCode 1: Two Sum

Problem Statement

Section link icon

LeetCode 1, Two Sum, is an easy-level challenge that’s a great starting point for learning algorithms. You’re given an array of integers called nums and a target integer target. The task is to find two numbers in the array that add up to the target and return their positions (indices) in a list of size 2. The problem guarantees exactly one solution exists, and you can’t use the same number twice (meaning the two indices must be different).

Constraints

  • 2 <= nums.length <= 10^4: The array has at least 2 elements, up to 10,000.
  • -10^9 <= nums[i] <= 10^9: Numbers can be positive, negative, or zero, with a wide range.
  • -10^9 <= target <= 10^9: The target also spans a wide range.
  • Only one valid pair exists.

Example

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

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: nums[1] + nums[2] = 2 + 4 = 6, so return [1, 2].

Input: nums = [3, 3], target = 6
Output: [0, 1]
Explanation: nums[0] + nums[1] = 3 + 3 = 6, so return [0, 1].

Understanding the Problem

Section link icon

The goal is to pick two different numbers from the array that sum to the target and return their indices. Since there’s exactly one solution, we don’t need to worry about multiple answers or no answers. The indices can be returned in any order, and we can’t reuse a number (e.g., if nums = [5] and target = 10, we can’t use 5 twice). We’ll explore two solutions:

  • Brute Force: Check every pair of numbers.
  • Hash Map: Use a fast lookup trick to find the pair.

Solution 1: Brute Force

Section link icon

Explanation

This method is like trying every possible combination to see what works. It’s simple but slow, especially for big arrays.

  1. Iterate Over All Pairs.
  • Go through each number, then check it with every number after it to find a pair that adds to the target. Use two loops: one for the first number, one for the second.

2. Check Sum.

  • Add the two numbers and see if they equal the target.

3. Return Indices.

  • If they match, return their positions right away.

Step-by-Step Example

Example 1: nums = [2, 7, 11, 15], target = 9

We have nums = [2, 7, 11, 15] and want two numbers that add to 9. Let’s find their positions.

  • Goal: Look for a pair that sums to 9 and get their indices.
  • Result for reference: Checking ahead, 2 + 7 = 9, at positions 0 and 1, so the answer is [0, 1].
  • Start: Use two pointers, like picking one number and testing it with others.
  • Step 1: Pick nums[0] = 2.
    • Test with nums[1] = 7: 2 + 7 = 9. That’s 9! We found it.
    • Positions are 0 and 1, so return [0, 1].
  • Stop: No need to keep going since we found the pair.
    • We could test 2 + 11 = 13 or 2 + 15 = 17, but 9 came first.

Example 2: nums = [3, 2, 4], target = 6

Now, nums = [3, 2, 4] and the target is 6.

  • Goal: Find two numbers adding to 6 and their spots.
  • Result for reference: 2 + 4 = 6, at positions 1 and 2, so the answer is [1, 2].
  • Start: Check pairs one by one.
  • Step 1: Pick nums[0] = 3.
    • Test with nums[1] = 2: 3 + 2 = 5. Too small.
    • Test with nums[2] = 4: 3 + 4 = 7. Too big.
  • Step 2: Pick nums[1] = 2.
    • Test with nums[2] = 4: 2 + 4 = 6. That’s it!
    • Positions are 1 and 2, so return [1, 2].
  • Stop: Found the pair, no need to check more.

Code

def twoSum(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 []  # Won’t happen with valid input

Complexity

  • Time Complexity: O(n²) – Two loops mean checking tons of pairs.
  • Space Complexity: O(1) – Just uses a couple of variables.

Efficiency Notes

It’s easy to follow but gets slow with big arrays. Checking every pair wastes time when we can be smarter.

Solution 2: Hash Map (Optimal)

Section link icon

Explanation

This method uses a trick with a hash map (like a fast notebook) to find the pair quickly. Instead of checking every combination, we look up what we need as we go.

  1. Initialize a Hash Map.
  • Make an empty notebook to store numbers and their positions.

2. Iterate Through the Array.

  • For each number, figure out what other number we need to hit the target.

3. Check the Hash Map.

  • Look in the notebook: if the needed number is there, we’ve got our pair. If not, add the current number and its spot.

4. Return Indices.

  • When we find the pair, return their positions.

Step-by-Step Example

Example 1: nums = [2, 7, 11, 15], target = 9

We have nums = [2, 7, 11, 15] and want two numbers adding to 9.

  • Goal: Find the pair that sums to 9 and their spots.
  • Result for reference: 2 + 7 = 9, at positions 0 and 1, so [0, 1].
  • Start: Use a notebook (hash map) that’s empty at first.
  • Step 1: Look at nums[0] = 2.
    • Need 9 - 2 = 7. Check the notebook: it’s empty. Add 2 at position 0 (notebook: {2: 0}).
  • Step 2: Look at nums[1] = 7.
    • Need 9 - 7 = 2. Check the notebook: 2 is there at position 0! Pair found.
    • Positions are 0 (from notebook) and 1 (current spot), so return [0, 1].
  • Stop: No need to check 11 or 15 since we’re done.

Example 2: nums = [3, 2, 4], target = 6

Now, nums = [3, 2, 4] and the target is 6.

  • Goal: Find two numbers adding to 6 and their positions.
  • Result for reference: 2 + 4 = 6, at positions 1 and 2, so [1, 2].
  • Start: Notebook is empty.
  • Step 1: Look at nums[0] = 3.
    • Need 6 - 3 = 3. Notebook’s empty. Add 3 at position 0 (notebook: {3: 0}).
  • Step 2: Look at nums[1] = 2.
    • Need 6 - 2 = 4. Notebook has 3, no 4. Add 2 at position 1 (notebook: {3: 0, 2: 1}).
  • Step 3: Look at nums[2] = 4.
    • Need 6 - 4 = 2. Notebook has 2 at position 1! Pair found.
    • Positions are 1 (from notebook) and 2 (current spot), so return [1, 2].
  • Stop: Found it, no more steps needed.

Example 3: nums = [3, 3], target = 6

For nums = [3, 3] and target 6.

  • Goal: Find the pair summing to 6.
  • Result for reference: 3 + 3 = 6, at positions 0 and 1, so [0, 1].
  • Start: Notebook is empty.
  • Step 1: Look at nums[0] = 3.
    • Need 6 - 3 = 3. Notebook’s empty. Add 3 at position 0 (notebook: {3: 0}).
  • Step 2: Look at nums[1] = 3.
    • Need 6 - 3 = 3. Notebook has 3 at position 0! Pair found.
    • Positions are 0 (from notebook) and 1 (current spot), so return [0, 1].
  • Stop: Done with the pair.

Code

def twoSum(nums: list[int], target: int) -> list[int]:
    num_map = {}
    for i in range(len(nums)):
        complement = target - nums[i]
        if complement in num_map:
            return [num_map[complement], i]
        num_map[nums[i]] = i
    return []  # Won’t happen with valid input

Complexity

  • Time Complexity: O(n) – One pass through the array, with fast lookups.
  • Space Complexity: O(n) – Notebook might hold most numbers.

Optimality Notes

This is way faster than brute force, cutting time from O(n²) to O(n) by using the notebook to avoid checking every pair.

Additional Example

Section link icon

For nums = [1, 5, 5, 2], target = 10:

  • Goal: Find two numbers adding to 10.
  • Result for reference: 5 + 5 = 10, at positions 1 and 2, so [1, 2].
  • Step 1: nums[0] = 1, need 9, add {1: 0}.
  • Step 2: nums[1] = 5, need 5, add {1: 0, 5: 1}.
  • Step 3: nums[2] = 5, need 5, found at 1, return [1, 2].
  • Stop: Pair found.

Edge Cases

Section link icon
  • Duplicates: nums = [3, 3], target = 6 – Hash map handles it fine.
  • Negatives: nums = [-1, -2], target = -3 – Works the same way.
  • Big Arrays: Hash map stays fast.

Final Thoughts

Section link icon
  • Brute Force: Simple but slow, good for learning.
  • Hash Map: Fast and smart, perfect for interviews and real use. It’s a key pattern for finding pairs quickly.