Two Sum
Watch the walkthrough
Open on InstagramProblem
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
// 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
console.log("Hello World");