Skip to content

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].
Example 2: 
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3: 
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints: 

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

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
TwoSum.js
/**
 * @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 the arr[j] since arr[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 the i parameters. So if we find arr[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
TwoSum.js
/**
 * @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
TwoSum.js
/**
 * @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.

References