The Two Sum Problem
The Two Sum problem is a popular coding challenge that appears frequently in technical interviews. The problem statement is straightforward: Given an array of integers nums
and an integer target
, return the indices of the two numbers that add up to the target. Each input would have exactly one solution, and you may not use the same element twice. Let’s dive into how to solve this problem efficiently using JavaScript.
Problem Breakdown
- Input: An array of integers (
nums
) and a single integer (target
). - Output: An array containing the indices of the two numbers from
nums
that add up totarget
.
The brute force approach would involve nested loops to check every pair of numbers, but this would result in an O(n^2) time complexity, which is not efficient for large datasets. Instead, we can solve this problem in O(n) time by utilising a hash map to store the indices of the numbers we’ve seen so far.
Solution Explanation
Here’s the solution using JavaScript:
javascriptCopy codevar twoSum = function(nums, target) {
let numIndices = new Map();
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (numIndices.has(complement)) {
return [numIndices.get(complement), i];
}
numIndices.set(nums[i], i);
}
throw new Error("No two sum solution");
};
Let’s break down the code step by step:
- Initialise a Map: We start by creating an empty map called
numIndices
. This map will store the numbers as keys and their corresponding indices as values.javascriptCopy codelet numIndices = new Map();
- Iterate through the Array: We loop through the array using a for loop.javascriptCopy code
for (let i = 0; i < nums.length; i++) {
- Calculate the Complement: For each element in the array, we calculate the complement by subtracting the current element from the target.javascriptCopy code
let complement = target - nums[i];
- Check if Complement Exists: We then check if the complement exists in the map. If it does, it means we have found the two numbers that add up to the target. We return their indices.javascriptCopy code
if (numIndices.has(complement)) { return [numIndices.get(complement), i]; }
- Store the Number and Index: If the complement does not exist in the map, we add the current number and its index to the map.javascriptCopy code
numIndices.set(nums[i], i);
- Error Handling: If no solution is found by the end of the loop, we throw an error indicating that no two sum solution exists.javascriptCopy code
throw new Error("No two sum solution");
Why This Approach Works
The key to this solution is the use of a hash map (implemented as a Map
in JavaScript). The map allows us to store and retrieve indices in constant time O(1). As we iterate through the array, we effectively reduce the problem of finding two numbers that add up to the target to a constant time lookup in the map.