1. Two Sum

Problem

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:

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

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

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

[!note]- Hint A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it’s best to try out brute force solutions just for completeness. It is from these brute force solutions that you can come up with optimizations.

[!note]- Hint So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

[!note]- Hint The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Solution

The brute force way is to check every pair of numbers, which is O(n^2). The trick is to trade space for time with a hash map: for each number, its complement is target - nums[i]. If the complement was already seen, we are done; otherwise we store the current number with its index and keep going. One pass, O(n) time, O(n) space.

TypeScript:

function twoSum(nums: number[], target: number): number[] {
  const hashmap: Map<number, number> = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (hashmap.has(complement)) {
      return [hashmap.get(complement)!, i];
    }

    hashmap.set(nums[i], i);
  }

  return [];
}

Python:

def twoSum(nums: list[int], target: int) -> list[int]:
    map = {}

    for i in range(len(nums)):
        complement = target - nums[i]

        if complement in map:
            return [map[complement], i]

        map[nums[i]] = i

    return []

Complexity Analysis

• Each element is visited once and hash map operations are O(1) on average

Notes

• The hash map stores value -> index, so the lookup for the complement is direct.
• Checking the complement before inserting the current number avoids matching an element with itself (important for cases like nums = [3, 3], target = 6, where both elements have the same value but different indices).
• Solved in JavaScript, TypeScript and Python; the idea is identical in all three.