Skip to content
Shubham JangleResources
Arrays & strings

Explore topics

Two Sum

Watch the walkthrough
Open on Instagram

Problem

Return two distinct indices whose values add up to target. Example: [3, 2, 4], target 6 -> [1, 2].

Approach and revision checks

The brute-force version checks every pair: O(n²) time, O(1) extra space. The Map version checks whether the complement was already seen before storing the current value: expected O(n) time, O(n) space. Test repeated values such as [3, 3] and a no-solution input.

Original repository source

Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.

1-two-sum.js

Original file on GitHub

// Brute
// TC: O(N*N) SC: O(1)
var _twoSum = function (nums, target) {
  let n = nums.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [-1, -1];
};

// Map, and find the remainder in map if exist, return its index
// TC: O(N), SC: O(N)
var twoSum = function (nums, target) {
  let n = nums.length;
  const mp = new Map();

  for (let i = 0; i < n; i++) {
    if (mp.has(target - nums[i])) {
      return [i, mp.get(target - nums[i])];
    } else {
      mp.set(nums[i], i);
    }
  }

  return [-1, -1];
};

const res = twoSum([3, 2, 4], 6);
console.log(res);

Repository warm-up

The folder also includes this introductory file.

0-hello-world.js

Original file on GitHub

console.log("Hello World");