lumænaut

LeetCode Solutions
#1 — Two Sum

From brute force to O(n) — a friendly journey for beginners

By Alberto Del Valle

(Read time ~4 min)

Color ASCII art: an outdated computer on a desk with a bookshelf in the background, suggesting a classic coding workspace.

Problem statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Example 2:

Example 3:

Constraints:

  • 2 <= nums.length <= 10⁴

  • -10⁹ <= nums[i] <= 10⁹

  • -10⁹ <= target <= 10⁹

  • Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

The naive way

You could take the first number, and then try adding it to every other number after it. If it matches the target, done! It's simple, honest, and it works. But it is also a slow solution.

Python

def twoSum_bruteforce(nums, target):
  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 []  # never reached because one solution exists

Initial complexity

If the array has n elements, the outer loop runs n times, and the inner loop would run about n/2 times on average. That gives us roughly n * (n-1)/2 operations, which translates to O(n²). If n = 10,000... that is about 50 million comparisons!

Using memory

Instead of checking every pair, we can remember what numbers we have seen and ask: Do I need a specific number to complete the target?

For each number x, the complement is target - x. If we've already seen that complement somewhere in the array, we found our pair! We just need a way to store the numbers we have passed and quickly look them up. That is where a hash map (also called hash table or dictionary) comes in—a data structure that lets you store key-value pairs and check if a key exists in O(1) average time.

Python

def twoSum_hashmap(nums, target):
    seen = {}  # key = number, value = index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Let’s trace example nums = [3,2,4], target = 6:

Step-by-Step Simulation: nums = [3,2,4] , target = 6
Step i num complement seen before Action seen after
1 0 3 3 {} Store {3:0} {3:0}
2 1 2 4 {3:0} Store {2:1} {3:0, 2:1}
3 2 4 2 {3:0, 2:1} Found 2 → return [1, 2] Finished → [1, 2]
Each row corresponds to one loop iteration. When the complement already exists in seen (step 3), we immediately return the pair of indices.

Beautiful, is it not? We only pass through the array once.

Final complexity

Time complexity: O(n) — we traverse the array once, and each hash map operation (insertion and lookup) is O(1) on average. Which also answers the follow-up question about whether we can do better than O(n²).
Space complexity: O(n) — in worst case we store almost all elements in the hash map before finding the pair.

Happy coding, and may your complexity always be low.
#2

References & further reading

Can't get enough from lumænaut? Read this...