CODEWITHSUNDEEP
javascriptarraysalgorithm
selected
selected

Reputation: 872

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

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

Example:

Given nums = [3, 2, 4], target = 6,

Because nums[1] + nums[2] = 2 + 4 = 6

return [1, 2].

Solution

var twoSum = function(nums, target) {
    for(let i = 0; i <= nums.length; i++){
        for(let j = 0; j <= nums.length; j++){
            if(nums[i] + nums[j] == target){
                return [i, j]
            }
        }
    }
};

The code above works in other cases but not this one.

Expected result [1,2]

Output [0,0]

For instance, I've tried to use a different array of numbers and a different target and it works even if you change the order of the numbers

Example:

New array: [15, 7, 11, 2], target = 9,

Output: [1, 3].

I don't understand what is wrong with the solution and I hope that someone can explain. Thanks

Upvotes: 5

Views: 94814

Answers (24)

Jeyam Thillai
Jeyam Thillai

Reputation: 91

Here simple and stright forward 

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {

for(i=0;nums.length>i;i++){ 
    var T = i
    for(j=0;nums.length>j;j++){
        if(T!=j){
              if(nums[T]+nums[j] == target){
            var number=[];
            number.push(T)
            number.push(j)
            return number
            
            }   
        }
        
        } 
}
}

Upvotes: 0

zohaib shahzad
zohaib shahzad

Reputation: 1

const twoSum = (nums, target) => {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const compliment = target - nums[i];
    if (map.has(compliment)) {
      return [map.get(compliment), i];
    }
    map.set(nums[i], i);
  }

  return [];
};

const nums = [3, 2, 4];
const target = 6;
console.log(twoSum(nums, target));

Explanation:

  • const map = new Map(); creates a new Map object.
  • map.has(complement); checks if the Map contains the complement.
  • map.set(nums[i], i); addsthe current element and its index to the Map.

The solution is efficient with a time complexity of O(n). Using the Map object makes the code more idiomatic and can provide better performance for large datasets.

Upvotes: 0

Satish Pashamnor
Satish Pashamnor

Reputation: 1

public class Main {
    public static void main(String[] args) {

        int a[] = { 2, 4, 6 };
        for (int i = 0; i <= a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] + a[j] == 10) {
                    int and[] = { i, j };
                    System.out.println(Arrays.toString(ans));
                }
            }
        }        
    }
}

Upvotes: 0

Ravi
Ravi

Reputation: 2340

function addNumber(num, target) {
   let arr = [];
   num.every((pv, pi) => {
      let diff = target - pv;
      let diffIdx = num.indexOf(diff);
      if (diffIdx !== -1 && diffIdx !== pi) {
          arr.push(pi,diffIdx)
          return false;
      }
      return true;
   });
    return arr;
  }

console.log(
    addNumber([4, 0, 1, 9, 7],4)
)

Upvotes: 0

Sumit Balani
Sumit Balani

Reputation: 1

Solution from my leetcode submission in Java. Top 75% in runtime, top 25% in memory. It is 0(n) however uses an external HashMap.

import java.util.HashMap; 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numbers= new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++){
            int cur = nums[i];
            numbers.put(cur, i);
        }
        for(int i=0; i<nums.length; i++){
            //check map for diff of target - cur
            int diff = target - nums[i];
            if(numbers.containsKey(diff) && numbers.get(diff)!=i){
                return new int[]{i, numbers.get(diff)};
            }
        }
        return null;
    }
}

Upvotes: 0

Theleeban C
Theleeban C

Reputation: 1

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    

<script>
 var twoSum = function(nums, target) {
    for(var i=0;i<nums.length;i++){
        for(var j=i+1;j<nums.length;j++){
        temp = nums[i]+nums[j];
        if(temp == target){
            return [nums[i],nums[j]]
        }
      }
    }
    
};
console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))
console.log(twoSum([3,3],6))
</script>
</body>
</html>

Upvotes: 0

DurrANI
DurrANI

Reputation: 31

Here's a simple method to solve this problem and its efficient using different type of inputs using JavaScript.
Like with input of ([3,3], 6) and its expected output will be [0,1] and input like ([3,2,4], 6) with expected output will be [2,4]

var twoSum = function (nums, target) {
   for (let i = 0; i <= nums.length; i++) {
     for (let j = 0; j <= nums.length; j++) {
       if (i !== j) {
         if (nums[i] + nums[j] === target) {
           return [i, j];
         }
       }
     }
   }
 };
 console.log(twoSum([3, 2, 4], 6));

Upvotes: 3

Md Ruhul Amin
Md Ruhul Amin

Reputation: 1

twoSummation = (numsArr, estTarget) => {
    for(let index = 0; index < numsArr.length; index++){
        for(let n = index+1; n < numsArr.length; n++){
            if(numsArr[index] + numsArr[n] == estTarget){
                return [index, n]
            }
        }
    }
}

console.log(twoSummation([2,7,11,15], 9))
console.log(twoSummation([3,2,4], 6))

Upvotes: 0

Prasun Mishra
Prasun Mishra

Reputation: 1

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indx =[]
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[j]==(target-nums[i]):
                    indx.append(i)
                    indx.append(j)
                    return indx

Upvotes: 0

Robert
Robert

Reputation: 7

var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++){
        for(let j = i+1; j < nums.length; j++){
            if(nums[i] + nums[j] == target){
                return [i, j]
            }
        }
    }
};

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

Upvotes: 0

Haniye Kashgarani
Haniye Kashgarani

Reputation: 1

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        comp = target - nums[i]
        if comp in nums:
            j = nums.index(comp)
                if(i!=j):
                    return [i,j]

Upvotes: 0

Adrian Moreno Garcia
Adrian Moreno Garcia

Reputation: 1

My solution:

  1. Create a Set
  2. Then loop the array for retrieve all the differences between the target number minus all the elements in array. Insert only which are positive (as is a Set, duplicates will not be included).
  3. Then iterates array again, now only compare if array elements is in the set, if yes take the index from i store in the index array and return it.
public static Object solution(int[] a, int target){
    Set<Integer> s = new HashSet<>();
    ArrayList<Integer> indexes = new ArrayList<Integer>();
    
    for (int e : a){
        Integer diff = new Integer(target - e);
        if(diff>0){
            s.add(diff);
        }
    }
    
    int i = 0;
    for (int e : a){
        if(s.contains(e)){
            indexes.add(i);
        }
        i++;
    }
    

    return indexes;
    
}

Upvotes: 0

Sanat Kumar
Sanat Kumar

Reputation: 92

For clearity console a & b in inner for loop . This will give you clear insight 

var twoSum = function(nums, target) {
var arr=[];
  
for(var a=0;a<nums.length;a++){
    for(var b=1;b<nums.length;b++){
        let c=nums[a]+nums[b];
       
        if(c== target  && a != b){
            
           arr[0]=a;
            arr[1]=b;
            
        }
    }
}   
  return arr;   
};

Upvotes: 0

Mena Nashaat
Mena Nashaat

Reputation: 1

var twoSum = function(nums, target) {
    for (var i = 0; i < nums.length; i++)
    {
        if(  nums.indexOf(target - nums[i]) !== -1)
        {
            return [i , nums.indexOf(target - nums[i])]
        }
    }
};

Upvotes: 0

himanshu
himanshu

Reputation: 56

we can solve this problem in O(n) by using the map/object. We can maintain a map or object which will save all values with index and then we can iterate the array and find target-nums[i] for each value and will find that value in map/object. let's see this by example:-

nums=[2,7,11,15]
target = 9;
then map/object will be 
mm={
2 : 0,
7: 1,
11: 2,
15: 3
}


then for each value, we will find diff and find that diff in map/object.
for i=0 diff= 9-2=7 and mm.has(7) is true so our answer is 2 and 7. 
for their index we can use mm.get(7) and i. 
return [mm.get(7), i]


var twoSum = function(nums, target) {
    let mm=new Map();
    for(let i=0;i<nums.length;i++){
        mm.set(nums[i],i);
    }
    let diff=0;
    let j;
    for(let i=0;i<nums.length;i++){
        diff=target-nums[i];
        if(mm.has(diff) && i!=mm.get(diff)){
           j=mm.get(diff);
            if(j>i){
                return [i,j];
            }else{
               return [j,i];
            }
        }
    }
};

Runtime: 76 ms, faster than 88.18% of JavaScript online submissions for Two Sum. Memory Usage: 41.4 MB, less than 13.32% of JavaScript online submissions for Two Sum.

Upvotes: 2

Mohit77
Mohit77

Reputation: 1

I suppose this could be a better solution. Instead of nesting loops, this provides a linear solution.

(PS: indexOf is kinda a loop too with O(n) complexity)

var twoSum = function (nums, target) {
    const hm = {}
    nums.forEach((num, i) => {
      hm[target - num] = i
    })

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

Upvotes: 0

nimish anand
nimish anand

Reputation: 1

var twoSum = function(nums, target) {
    var numlen = nums.length;
    for(let i=0; i<=numlen; i++){
        for(let j=i+1;j<numlen;j++){
            var num1 = parseInt(nums[i]);
            var num2 = parseInt(nums[j]);
            var num3 = num1 + num2;
            if(num3 == target){
            return[i,j]
            }
        }
    }
    
    
};

Upvotes: 0

Danilo Sampaio
Danilo Sampaio

Reputation: 41

Another efficient solution way to solve this problem with an O(n) time complexity is not using nested loops. I commented the steps, so JS developers can easy understand. Here is my solution using golang:

func twoSum(intArray []int, target int) []int {
    response := []int{-1, -1}  // create an array as default response

    if len(intArray) == 0 {  // return default response if the input array is empty
        return response
    }

    listMap := map[int]int{} // create a Map, JS => listMap = new Map()

    for index, value := range intArray { // for loop to fill the map
        listMap[value] = index
    }

    for i, value := range intArray { // for loop to verify if the subtraction is in the map
        result := target - value
        if j, ok := listMap[result]; ok && i != j { // this verify if a property exists on a map in golang. In the same line we verify it i == j.
            response[0] = i
            response[1] = j
            return response
        }
    }

    return response
}

Upvotes: 0

Dasoju Shiva
Dasoju Shiva

Reputation: 23

var twoSum = function(nums, target) {
    for(var i=0;i<nums.length;i++){
        for(var j=i+1;j<nums.length;j++){
        temp = nums[i]+nums[j];
        if(temp == target){
            return [i,j]
        }
      }
    }
    
};


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

This works perfectly and the Runtime: 72 ms lesser than 84ms

Upvotes: 0

Pranjal Successena
Pranjal Successena

Reputation: 967

You can use a very simple technique.
Basically, you can check if the difference of target & the element in the current iteration, exists in the array.

Assuming same index cannot be used twice

nums = [3, 2, 4], target = 6
nums[0] = 3
target = 6
diff = 6 - 3 = 3
nums.indexOf[3] = 0 // FAILURE case because it's the same index

// move to next iteration
nums[1] = 2
target = 6
diff = 6 - 2 = 4
nums.indexOf(4) = 2 // SUCCESS '4' exists in the array nums
// break the loop

Here's the accepted answer by the leetcode.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let index = 0; index < nums.length; index++) {
        const diff = target - nums[index];
        const diffIndex = nums.indexOf(diff);
        // "diffIndex !== index" takes care of same index not being reused
        if (diffIndex !== -1 && diffIndex !== index) {
            return [index, diffIndex];
        }
    }
};

Runtime: 72 ms, faster than 93.74% of JavaScript online submissions for Two Sum.
Memory Usage: 38.5 MB, less than 90.55% of JavaScript online submissions for Two Sum.

Can anybody help me in reducing the memory usage also?

Upvotes: 12

Angie Badillo
Angie Badillo

Reputation: 29

var twoSum = function(nums, target) {
    
   for(let i=0; i<nums.length; i++){
       for(let j=i+1; j<nums.length; j++){
           if(nums[j] === target - nums[i]){
              return [i, j];
           }
       }
   }
};

Upvotes: 1

Mridul
Mridul

Reputation: 266

var twoSum = function (nums, target) {
var len = nums.length;
for (var i = 0; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
        if (nums[i] + nums[j] == target) {
            return [i,j];
        }
    }
  }
};

Upvotes: 0

Code Maniac
Code Maniac

Reputation: 37765

I don't understand what is wrong with the solution and I hope that someone can explain ?

Here you're both inner and outer loop start from 0th so in the case [3,2,4] and target 6 it will return [0,0] as 3 + 3 is equal to target, so to take care of same index element not being used twice created a difference of 1 between outer and inner loop

Make outer loop to start from 0th index and inner loop with value i+1

var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++){
        for(let j = i+1; j < nums.length; j++){
            if(nums[i] + nums[j] == target){
                return [i, j]
            }
        }
    }
};

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

Upvotes: 8

Jb31
Jb31

Reputation: 1391

Your solution works as expected. For nums = [3, 2 ,4] and target = 6, [0, 0] is a valid solution for the outlined problem as nums[0] + nums[0] = 3 + 3 = 6.

If you need two different indices (In my understanding this is not required by the task) you can add an additional check for inequality (nums[i] + nums[j] == target && i != j).

Upvotes: 1

Related Questions