This content originally appeared on DEV Community and was authored by Diganta Chaudhuri
One Of the most popular problem of leetcode is 2 sum. This problem can be solved through many ways like 2 pointers, hashing... out of them if Input array is not sorted then the hashing approach is better in terms of Time Complexity. If input array is sorted then the two pointer approach will be better in that case Space Complexity will be reduced down to O(1).
The Hashing approach is:
var twoSum = function(nums, target) {
const mp = new Map();
for (let i = 0;i < nums.length;i++) {
let rem = target - nums[i];
if (mp.has(rem)) {
return [i, mp.get(rem)];
}
mp.set(nums[i], i);
}
return [-1,-1];
};
The time complexity of this approach is O(N),
space complexity is O(N)
If the input array is sorted then we can farther optimise this solution by using 2 pointers
we can place 2 pointers in the both ends
var twoSum = function(nums, target) {
let i = 0, j = nums.length-1;
while (i < j) {
const sum = nums[i]+nums[j];
console.log({i,j});
if (sum == target) {
return [i, j];
} else if (sum < target) {
i++;
} else {
j--;
}
}
return [-1, -1];
};
NOTE: This solution will not work in leetcode because we have to return the indexes so if we sort the input array then it will messed up the indexes.
The Time Complexity of this approach is O(N) and Space Complexity is O(1).
This content originally appeared on DEV Community and was authored by Diganta Chaudhuri
Diganta Chaudhuri | Sciencx (2022-06-16T13:04:11+00:00) Blind 75 – 1. Two Sum Javascript. Retrieved from https://www.scien.cx/2022/06/16/blind-75-1-two-sum-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.