Two Sum
Problem
Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up totarget
.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.
Pseudocode
- loop thorugh the array of integers
- find the complement of the current integer
- complement = target - nums
- store complement in a Map as a key, with index with value
- [k, v] = [complement, i]
- if the current integer is found in the complement
- return current index and index of complement
Solution
var twoSum = function (nums, target) {
let map = new Map();
let result = [];
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
// find complement for nums[i]
if (map.has(nums[i])) {
result.push(i, map.get(nums[i]));
return result;
} else {
map.set(complement, i);
}
}
};
Time and Space Complexity
Time
Loops through the array once - O(N)
Map operations are constant time
Total - O(N)
Space
Stores complement of each element in a Map
Worst case scenario is that complement is in the last position of the array
Total - O(N)
Last updated