DEV Community 👩‍💻👨‍💻

Somnath.geek
Somnath.geek

Posted on

Two Sum solved in javascript

Two Sum : Javascript

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].

Code:

 var twoSum = function(nums, target) {
    //hash table
    var hash = {};

    for(let i=0; i<=nums.length; i++){
      //current number
        var currentNumber = nums[i];
        //difference in the target and current number
        var requiredNumber = target - currentNumber;
        // find the difference number from hashTable
        const index2 = hash[requiredNumber];

        // if number found, return index 
        // it will return undefined if not found
        if(index2 != undefined) {
            return [index2, i]
        } else {
           // if not number found, we add the number into the hashTable
            hash[currentNumber] = i;

        }
    }
};

In detail:

  • Declare a empty hash table
  • Loop through the array
  • Store the current number in a variable
  • Find the difference between the the target number and the current number
  • Search for the difference number from the hash table
  • If number found, return the index of the first number and the search number
  • If not found, add the number into the hash table and continues for loop checking.

Conclusion:

Hashmap is the optimal solution as the average search time complexity is O(1)

Runtime Memory
84 ms 35.5 MB

Top comments (5)

Collapse
 
bhanuchhabra7 profile image
Bhanu Chhabra

This is O(N) complexity, not O(1)
There is for loop, and regardless of list construct, a non breaking for loop traversal is O(N).

Collapse
 
linuxnerd profile image
Abhishek Prakash

I think he meant the time complexity of search operation on a hash table is O(1) and not for the solution.

Collapse
 
bhanuchhabra7 profile image
Bhanu Chhabra

Well that is quite confusing. Atleast on my part it is.
People report the solution's complexity with subparts to prove some point.

But just pointing complexity of just 1 sub part and not talking about whole algo/solution is somewhat unusual.

Collapse
 
bhanuchhabra7 profile image
Bhanu Chhabra

Also the conclusion doesn't matches with any content in description.

The base of conclusion should be discussed in opening statements.

Collapse
 
laith00x profile image
laith00x

hey, can you please explain why in the return statement (return [index2, i]) you added 'i'? what is the value of i and how did it get the correct value? thanks in advance

👉 Help make DEV better

Start a new GitHub Discussion in the Forem repo.