Refactor Nested For Loop

user_12960303 0
Viewed 1097

Instructions

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

How can I refactor this to eliminate the nested for-loop? I'd like to get the time complexity down.

Code

const twoSum = function(nums, target) {
    for(let i in nums){
      for(let j in nums) {
        if(nums[i] + nums[j] === target && nums[i] != nums[j]) {
            return [i, j];
        }
      }
    }
};

console.log(twoSum([2, 7, 11, 15], 9));

nested-loops for-loop arrays javascript
3 Answers

You can save the difference of each element with the target inside an object with the result as keys and the index as values. This will make checking for the existence of an element inside an object without looping though the whole content. In a different loop check if the array elements exist in the object, if they do then you have got the pair. The additional condition is to prevent comparing an element with itself. 

const twoSum = function(nums, target) {  
  const temp = {};
  for(let i=0; i<nums.length; i++) {
    temp[target - nums[i]] = i;
  }

  for(let i=0; i<nums.length-1; i++) {
    if(temp[nums[i]] && temp[nums[i]] !== i) {
      return [i, temp[nums[i]]]
    }
  }
};

console.log(twoSum([2, 11, 7, 17], 9));
console.log(twoSum([1, 3, 4, 2], 6));

user_57919970

You can solve this problem with O(n) time. The condition is to solve by this approach is that the array must be sorted.

let twosum = (arr, x) => {
  let s = 0,
    e = arr.length - 1;
  let loc = [];

  while (s < e) {
    if (arr[s] + arr[e] === x) {
      loc.push([s,e]);
      s++;
      e--;
    } else if (arr[s] + arr[e] < x) {
      s++;
    } else {
      e--;
    }
  }

  return loc;
};

console.log(twosum([1, 2, 3, 4, 5, 7, 8], 9));
console.log(twosum([2, 7, 11, 15], 9));

The algorithm behind this if anyone interested:

1.   Set s value as 0
2.   Set e value as last index say (arr.length - 1)
3.   While s is less than e i.e not pass one another
4.   Check if arr[s] + arr[e] === x then we find it.
4.1. increment s value by 1 as there is no possibility to find any combination before the current s value
4.2. decrement e value by 1 as there is no possibility to find any combination after the current e value
4.3. collect the indexes where the match found.
5.   If arr[s] + arr[e] < x
5.1  increment s as there is no possibility to find any combination before the current s value. But there still has the possibility for the e value to get a match.
6.   If arr[s] + arr[e] > x
6.1  decrement e as there is no possibility to find any combination after the current e value. But there still has the possibility for the s value to get a match.
user_46107400

Since this appears to be homework, I'll make a couple suggestions without giving away a complete solution:

  • Your current code is repeating index checks. For example, you're looping over indices [0,1] and [1,0], which will always have the same sum since a+b = b+a. Instead, I would suggest your loop for i go from 0 to len-1, and your loop for j go from i+1 to len-1. That way you will never duplicate checks.
  • Part of your current check includes the condition that nums[i] != nums[j], but your problem doesn't state that two values in the array can't be the same. Is it possible to call this function with values like toSum([1, 4, 4], 8) such that 4+4=8? If so, then you can remove the nums[i] != nums[j] check to save time.
  • It's not clear if the array provided is sorted. If it's not, then you could create a tracking variable to account for values you've already checked, and prevent checking them on future iterations. For example, if you already compared the value 4 against all other values in the array and found no solution, then if you encounter 4 later in the array, there is no reason to check it.
user_1072770
Related