Two Sum

(#1), Easy

Category: Array, Hash Table

Problem Statement

Given an array of integers `nums` and an integer `target`, return the 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.

Examples

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

Output: [0, 1]

Explanation: Because nums[0] + nums[1] == 9.

Approach

Approach 1: Brute Force

  • Loop through each element in the array.
  • For every element, subtract it from the target.
  • Search the remainder in the rest of the array using another loop.
  • If found, return the indices.
// 🔹 Approach 1: Brute Force
var twoSum = function(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    let diff = target - nums[i];
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] === diff) {
        return [i, j];
      }
    }
  }
};

Approach 2: Optimal using Hash Map

  • Initialize a hash map to store each element's value and its index.
  • Loop through the array.
  • For each number, calculate the complement: `target - current number`.
  • Check if the complement exists in the map.
  • If yes, return the stored index and current index.
  • Otherwise, add the current number and index to the map.
// 🔹 Approach 2: Optimal using Hash Map
var twoSum = function(nums, target) {
  const map = new Map();

  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);
  }
};

Complexity

Time: O(n) for optimal approach (hash map); O(n²) for brute force

Space: O(n) – for hash map; O(1) for brute force

Watch Explanation

📎 Resources