1. TwoSum¶
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
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.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Constraints:
Only one valid answer exists.
Problem Analysis¶
First make sure you note the problem statement that you are looking to find only one pair of indices in an array, so you need to stop once you find the first solution.
Next note that the numbers are integers and you may not use the same index as a result. For example when arr=[3,2,4]
and target=6
then [0,0]
won't be allowed.
An easy observation is that you will have to iterate over the whole input array at least once, since there is a chance that the only indices will be at the end of the array. This gives us time complexity of \(\Omega(n)\) where n
length of the input array.
Solutions¶
Brute Force¶
The most straightforward solution attempt is to loop each of the element of the array with the rest while trying to satisfy the search target condition. For example using two loops starting at indices i,j
where j > i
until the end of the input array [(0,1), (0,2),...(arr.length-1, arr.length-1)]
then use those indices to find arr[i]+arr[j] == k
. The following program shows how to implement this approach:
Solution using Brute Force
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function twoSum(nums, target) {
// First loop goes for each first element
for (let i = 0; i < nums.length; i++) { // O(n)
// Second loop goes for each second element of the rest of array. Make sure we don't start with the same i.
for (let j = i + 1; j < nums.length; j++) { // O(n)
// Check if adding those elements equal to the target
if (nums[i] + nums[j] === target) { // O(1)
return [i, j];
}
}
}
// Return an empty array as we haven't found any elements that add up to the target element
return [];
}
Verify that the algorithm is correct and especially the loop indices do not skip parts of the array. The time complexity of the algorithm is \(O(n^2)+c\) as we iterate twice over the same input array.
Using a HashTable¶
We can improve the Brute force implementation by trading space with time. As we iterate over each element we note that:
- The difference
target-arr[i]
represents thearr[j]
sincearr[i] + arr[j] == target
. - Since we know the current index of the element the current value and the target we can calculate their differences and store them in a memory for later.
- We can use a HashTable with index as
target-arr[i]
and value thei
parameters. So if we findarr[j]
we can return[i, j]
. This saves us from doing the extra loop.
The following program shows how to implement this approach:
Solution with HashTable
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function twoSum(nums, target) {
// Keeping track of the last seen differences using a hash table.
const cache = new Map();
// Only one loop needed for
for (let i = 0; i < nums.length; i += 1) { // O(n)
// Check the cache for the arr[j]
if (cache.has(nums[i])) { // O(1)
return [cache.get(nums[i]), i];
} else {
// Add their difference (target-nums[i]) to the cache for later
cache.set(target - nums[i], i); // O(1)
}
}
// Return an empty array as we haven't found any elements that add up to the target element
return [];
}
The time complexity of the algorithm is \(O(n)+c\) now as we iterate only once over the same input array. The space complexity is \(O(n)\) as we might store the whole array in the hash table in case we don't find a solution.
Additional Thoughts¶
What if duplicates exists?¶
If duplicates exist then obviously you cannot use the same value for the result so you need to check if arr[i]==arr[j]
. This will happen when arr[i]=arr[j]=target/2
. If this is true then you simply ignore those indices and move on to the next ones.
Solution with No Duplicates
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function twoSum(nums, target) {
// Keeping track of the last seen differences using a hash table.
const cache = new Map();
// Only one loop needed for
for (let i = 0; i < nums.length; i += 1) { // O(n)
// Check the cache for the arr[j] while skipping duplicate entries
if (nums[i] != target / 2 && cache.has(nums[i])) { // O(1)
return [cache.get(nums[i]), i];
} else {
// Add their difference (target-nums[i]) to the cache for later
cache.set(target - nums[i], i); // O(1)
}
}
// Return an empty array as we haven't found any elements that add up to the target element
return [];
}
console.log(twoSum([1,1,1,2,3,3,4], 6));
What if I sort the array first?¶
If you sort the array then you lose all the information about the original array indices making it harder to restore it back. That's not a good approach in general.
Related Techniques¶
- Using a HashTable to trade time with space.