4
\$\begingroup\$

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.

Question link: https://leetcode.com/problems/two-sum/

/**
 * @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: enter image description here

\$\endgroup\$
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – pacmaninbw Nov 3 at 16:07
  • 2
    \$\begingroup\$ For downvoters, working code that does not peform within time limits is valid for CodeReview and should not be downvoted or closed. \$\endgroup\$ – konijn Nov 3 at 18:15
6
\$\begingroup\$

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 [];
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – iRohitBhatia Nov 4 at 11:24
  • \$\begingroup\$ @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!? \$\endgroup\$ – Ricardo Barroso Nov 4 at 11:59
  • \$\begingroup\$ @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. \$\endgroup\$ – Blindman67 Nov 4 at 12:03
  • 1
    \$\begingroup\$ @iRohitBhatia yeah, I wanted to help fixing it. It seems Blindman67 did not accept my changes but I think he will fix it. \$\endgroup\$ – Ricardo Barroso Nov 4 at 12:12
  • 1
    \$\begingroup\$ Thanks Ricardo, Appreciate you answering and then helping out in the comment section :) \$\endgroup\$ – iRohitBhatia Nov 4 at 12:14
0
\$\begingroup\$

@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:

enter image description here

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you explain why your solution is better than the original. Code review is primarily about improving the askers code. \$\endgroup\$ – pacmaninbw Nov 4 at 4:00
  • \$\begingroup\$ @Ricardo Thanks, I thought swift would be like alien to me but luckily I can make sense out of it. Yeah \$\endgroup\$ – iRohitBhatia Nov 4 at 10:44
  • \$\begingroup\$ @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]. \$\endgroup\$ – Ricardo Barroso Nov 4 at 11:53
  • 1
    \$\begingroup\$ Please use the edit functionality to update your post and include details. Also note that referring to issues in other answers in your answer is discouraged. Instead use the comments under the answer you refer to for discussion about the answer. \$\endgroup\$ – Vogel612 Nov 4 at 13:34
  • \$\begingroup\$ @Vogel612 I did add some detail about the original solution. Thanks for the tips about commenting other solutions, makes sense and I'll take them in account for future comments. \$\endgroup\$ – Ricardo Barroso Nov 4 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.