Easy#1

Two Sum

ArrayHash Table

Two Sum

The Two Sum problem is a classic introduction to array manipulation and the importance of efficient data structures.

The Challenge

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.

Approaches

1. Brute Force

The simplest approach is to loop through each element $x$ and find if there is another value that equals $target - x$. As we need to check every possible pair, the time complexity is $O(n^2)$.

2. One-pass Hash Map

We can reduce the time complexity by trading space for speed. As we iterate through the array, we store each number's value and its index in a hash map. For each current number, we check if its complement ($target - current$) is already in the map.

Interactive Visualization

Below, you can see how the One-pass Hash Map approach works step by step. Notice how the map is built as we go, allowing us to find the complement in $O(1)$ time.

One-pass Hash Map

Target: 9

curr

112

153

Hash Map (Value → Index)

Empty

Current value is 2. Looking for complement 7 in hash map. Not found. Adding 2 to map.

Step 1 / 2

Speed

Follow-up

Can you come up with an algorithm that is less than $O(n^2)$ time complexity? (Spoiler: we just did with the hash map!)

Solutions

1Brute Force

TimeO(n²)

SpaceO(1)

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

typescript

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
};

python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

2One-pass Hash Map

TimeO(n)

SpaceO(n)

Store the numbers we have seen so far in a hash map. For each number, check if its "complement" already exists in the map.

typescript

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return [];
};

python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {} # val : index
        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i