Leetcode - 1. Two Sum
Leetcode - 1. Two Sum: Efficient Solutions in JavaScript
Finding pairs of numbers within an array that sum to a specified target is a classic coding interview problem. This post explores two efficient approaches to solve LeetCode's "Two Sum" problem using JavaScript: one leveraging the power of hash maps, and another employing a two-pointer technique.
Using a Hash Map (Optimal Solution)
A hash map (or dictionary in Python) provides an optimal solution for this problem due to its constant-time average complexity for lookups. This approach minimizes the time it takes to find the solution, especially when working with large datasets.
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
let myMap = new Map();
for (let i = 0; i < nums.length; i++) {
myMap.set(nums[i], i);
}
for (let i = 0; i < nums.length; i++) {
let remaining = target - nums[i];
if (myMap.has(remaining) && myMap.get(remaining) !== i) {
return [i, myMap.get(remaining)];
}
}
};
This code first populates a hash map with each number in the input array and its index. Then, it iterates through the array, calculating the 'remaining' value needed to reach the target. By checking if the 'remaining' value exists in the map, and ensuring it's not the same index, we efficiently locate the pair.
Example: Given nums = [2, 7, 11, 15] and target = 9, the function would return [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.
Using Pointers (Alternative Approach)
While the hash map offers optimal performance, a two-pointer approach provides an alternative solution, particularly useful when the input array is already sorted. This method trades off some performance for a potentially simpler implementation.
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let left = 0;
let right = 1
while(left <= nums.length-1){
if(nums[left] + nums[right] === target){
return [left,right]
}else if (right === nums.length-1){
left++;
right = left+1;
}
else{
right++;
}
}
};
Note: This two-pointer approach assumes the input array nums is sorted. If it's not sorted, you'll need to sort it first, adding to the overall time complexity.
Example: Given a sorted nums = [2, 7, 11, 15] and target = 9, the function would efficiently find and return [0, 1].
Conclusion
Both hash map and two-pointer approaches effectively solve the Two Sum problem. The hash map offers superior average-case time complexity (O(n)), making it ideal for larger datasets. The two-pointer method, efficient for sorted arrays, presents a concise alternative. Choosing the best approach depends on the specific constraints and characteristics of your input data.
Related Articles
Software Development
Unveiling the Haiku License: A Fair Code Revolution
Dive into the innovative Haiku License, a game-changer in open-source licensing that balances open access with fair compensation for developers. Learn about its features, challenges, and potential to reshape the software development landscape. Explore now!
Read MoreBusiness, Software Development
The Future of Digital Credentials in 2025: Trends, Challenges, and Opportunities
Digital credentials are transforming industries in 2025! Learn about blockchain's role, industry adoption trends, privacy enhancements, and the challenges and opportunities shaping this exciting field. Discover how AI and emerging technologies are revolutionizing identity verification and workforce management. Explore the future of digital credentials today!
Read MoreSoftware Development
Unlocking the Secrets of AWS Pricing: A Comprehensive Guide
Master AWS pricing with this comprehensive guide! Learn about various pricing models, key cost factors, and practical tips for optimizing your cloud spending. Unlock significant savings and efficiently manage your AWS infrastructure.
Read More
