Great explanation. Under a time constraint pressure I would have undoubtedly gone with the nested arrays solution. The optimized solution you have there is better (considering the problems rules we must abide by). But after thinking about it, the first loop you have there is unnecessary because you are just remapping it to quickly find the index of the difference between the array number and the goal. Array.prototype.indexOf will do that for you. Here is an even more optimized solution coupled with an early return.
const input = [1, 3, 10, 11, 13];
function twoSum(array, target) {
for (let i = 0; i < array.length; i++) {
const diffIndex = array.indexOf(target - array[i]);
if (diffIndex >= 0 && diffIndex !== i) {
return [i, diffIndex];
}
}
return []; // no solution found
}
No it does not. It correctly outputs [0, 4]. But I see where you are going with it, change that last value from 9 to 10 so that only the two 5 values will work. It still outputs [2, 1] which are the indices of both 5 values. Why? Because even though it won't catch it on the first five it comes across it will catch it on the second. But you bring up a good point. Can we optimize this so that you don't have to keep going through the array if the solution is a duplicate value that is AFTER the index you are currently on? Yes. And here is my solution for that.
function twoSum(array, target) {
for (let i = 0; i < array.length; i++) {
const searchArray = [...array];
searchArray.splice(i, 1);
let diffIndex = searchArray.indexOf(target - array[i]);
if (diffIndex >= 0) {
return [i, diffIndex >= i ? diffIndex + 1 : diffIndex - 1];
}
}
return []; // no solution found
}
Nice solution! I like the early return, that way the solution doesn't double up on the numbers.
However, I think that indexOf actually runs in O(n) time, because it has to search through the array for the specified number. That means your solution is still O(n^2), because it has two nested loops.
I think the most optimized would be a mix of both, so:
Thanks for your reply! Since it was more of a conceptual answer, I didn't run it before commenting. I have now; I figured out the error and fixed it.
For those interested, the issue was that a return statement in a forEach loop actually just returns inside the loop, and doesn't return in the function. To fix it, I converted it to a plain for loop.
As for the 5 people who liked it, I'm sure they appreciated the concept behind the comment and could see past any logic errors. I don't think that quite makes them fools.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Great explanation. Under a time constraint pressure I would have undoubtedly gone with the nested arrays solution. The optimized solution you have there is better (considering the problems rules we must abide by). But after thinking about it, the first loop you have there is unnecessary because you are just remapping it to quickly find the index of the difference between the array number and the goal.
Array.prototype.indexOf
will do that for you. Here is an even more optimized solution coupled with an early return.const input = [1, 3, 10, 11, 13];
function twoSum(array, target) {
for (let i = 0; i < array.length; i++) {
const diffIndex = array.indexOf(target - array[i]);
if (diffIndex >= 0 && diffIndex !== i) {
return [i, diffIndex];
}
}
return []; // no solution found
}
console.log(twoSum(input, 13)); // outputs [1,2]
codesandbox.io/s/keen-browser-hmsp...
indexOf uses forloop internally so the time complexity of your code becomes O(n^2).
Instead use map for this solution.
Your solution will fail with test input
[1, 5, 5, 4, 9]
10
since method indexOf stops immediately at the first match
No it does not. It correctly outputs [0, 4]. But I see where you are going with it, change that last value from 9 to 10 so that only the two 5 values will work. It still outputs [2, 1] which are the indices of both 5 values. Why? Because even though it won't catch it on the first five it comes across it will catch it on the second. But you bring up a good point. Can we optimize this so that you don't have to keep going through the array if the solution is a duplicate value that is AFTER the index you are currently on? Yes. And here is my solution for that.
Nice solution! I like the early return, that way the solution doesn't double up on the numbers.
However, I think that
indexOf
actually runs inO(n)
time, because it has to search through the array for the specified number. That means your solution is stillO(n^2)
, because it has two nested loops.I think the most optimized would be a mix of both, so:
Thanks for your reply! Since it was more of a conceptual answer, I didn't run it before commenting. I have now; I figured out the error and fixed it.
For those interested, the issue was that a
return
statement in aforEach
loop actually just returns inside the loop, and doesn't return in the function. To fix it, I converted it to a plainfor
loop.As for the 5 people who liked it, I'm sure they appreciated the concept behind the comment and could see past any logic errors. I don't think that quite makes them fools.