# two-sum algorithm

Can someone help me in optimizing the code here?

This is the original question

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.

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const hashMapArray = {}
for (let i=0; i<nums.length; i++) {
const num = nums[i]
for (let index in hashMapArray) {
if (hashMapArray[index] + num  === target) {
return [index, i]
}
}
hashMapArray[i] = num
}
return []
}


Frankly, I was expecting my code to be optimized but then this what I got as a result and I was kinda heartbroken

How can I make it better?

Results:

• For those voting to close based on LCC, while there isn't a lot here, this is all the code the poster had to write, the rest is supplied by the programming challenge itself. – pacmaninbw Nov 3 '19 at 16:07
• For downvoters, working code that does not peform within time limits is valid for CodeReview and should not be downvoted or closed. – konijn Nov 3 '19 at 18:15

I can not work out why you are iterating the mapped values. The point of mapping the values is so you do not need to search them.

Rather than use an object to map the values you can also use a Map, though there is not much of a performance gain.

The following at most will only iterate each item once and thus save you a significant amount of CPU time.

function twoSum(nums, target) {
const map = new Map(), len = nums.length;
var i = 0;
while (i < len) {
const num = nums[i], val = target - num;
if (map.has(val)) { return [i, map.get(val)] }
map.set(num, i);
i++;
}
return [];
}


To save memory you can use the following. It will be slower than the above function however it will still be a lot faster than your function as the inner loop only search from the outer loops current position.

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

• Hey, Thanks for such an amazing answer. I am just about trying to comprehend your code but before that I gave it a spin and your code failed on submit. For this input [3,2,4], 6 the expected output is [1,2] but yours output was [0,0] – iRohitBhatia Nov 4 '19 at 11:24
• @Blindman67, like I also answered to @pacmaninbw, @iRohitBhatia is right, both your solutions fail that test. And the 2nd solution does have a runtime error on line 5 where it's num[i] should be nums[i]. I tried to edit and fix it, but StackOverflow does not allows me to submit it since it says I have to change at least 6 characters when I only need to add one!? – Ricardo Barroso Nov 4 '19 at 11:59
• @iRohitBhatia Your question was not clear 3 + 3 = 6 as does 2 + 4 so technically [0,0] is correct however it is a simple change to avoid the same index. I will change the code now. – Blindman67 Nov 4 '19 at 12:03
• @iRohitBhatia yeah, I wanted to help fixing it. It seems Blindman67 did not accept my changes but I think he will fix it. – Ricardo Barroso Nov 4 '19 at 12:12
• Thanks Ricardo, Appreciate you answering and then helping out in the comment section :) – iRohitBhatia Nov 4 '19 at 12:14

@iRohitBhatia your original solution creates an hash map without needing it and repeats the "sum" operation in the 2nd iteration also without need.

Here you have the Swift version I did code to solve it initially:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<(nums.count-1) {
let matchValue = target - nums[i]

for j in (i+1)..<nums.count {
if nums[j] == matchValue {
return [i, j]
}
}
}

return []
}


which I then translated to this JavaScript code:

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

for (let j = i+1; j < nums.length; j++) {
if (nums[j] == matchValue) {
return [i, j];
}
}
}

return [];
};


and after submitting it on LeetCode I got the following results:

• Can you explain why your solution is better than the original. Code review is primarily about improving the askers code. – pacmaninbw Nov 4 '19 at 4:00
• @Ricardo Thanks, I thought swift would be like alien to me but luckily I can make sense out of it. Yeah – iRohitBhatia Nov 4 '19 at 10:44
• @pacmaninbw, I'm sorry you're right, I solved it without taking the provided solutions above. Answering to you, the @iRohitBhatia solution creates an hash map without needing it and repeats the "sum" operation in the 2nd iteration without need. Regarding @Blindman67 solutions, none of them are passing the LeetCode tests, the last one even have a runtime error on line 5 where it's num[i] should be nums[i]. And even fixing it, both solutions fail to pass a test with [3,2,4] and 6 (target) inputs, where the expected solution is [1,2] and we get [0,0]. – Ricardo Barroso Nov 4 '19 at 11:53