Re: LeetCode Problem #1 - Two Sum - Improve and/or discuss.

I did not benchmark this yet - but this should be faster (it passes your tests):

sub twosum_NetWallah{
  my ($inp, $target)=@_;
  my %targ_idx = map { $inp->[$_] => $_ } 0..$#$inp;

  for (0..$#$inp){
     next unless defined ( my $other=$targ_idx{ $target - $inp->[$_] }
+ );
     next if $other == $_;
     return [ $other > $_ ? ($_, $other) : ($other, $_) ];
  }
  return undef;
}    

# Test NetWallah..
for my $test (@tests) {
    is_deeply
        sort_arrayref(twosum_NetWallah ($test->[INPUT], $test->[TARGET
+])),
        sort_arrayref($test->[EXPECTED]);
}
[download]

UPDATE 1: removed buggy " -1" from (0..$#$inp -1); deleted unnecessary variable @solutions.

UPDATE 2: I did try to benchmark the code - kcott's runs ~ 40% faster, so I was surprised!
However- After adding this test case:

    [[-5,-3,1,4,7], 1, [1,3]],
[download]

kcott's code fails that test case, but mine passes.
Note - that new test case does meet the problem definition (array of integers), which can have negative numbers.
Also - kcott's code assumes and takes advantage of the input being sorted - input order is NOT specified in the problem definition.

BTW - thanks for setting up this challenge!

"If you had better tools, you could more effectively demonstrate your total incompetence."

Comment on Re: LeetCode Problem #1 - Two Sum - Improve and/or discuss. Select or Download Code

Replies are listed 'Best First'.
Re^2: LeetCode Problem #1 - Two Sum - Improve and/or discuss. by kcott (Archbishop) on Jan 25, 2022 at 20:12 UTC
G'day NetWallah, "After adding this test case: `[[-5,-3,1,4,7], 1, [1,3]],` kcott's code fails that test case, but mine passes." Well spotted and thanks for reporting the bug. I had added `next INNER if $input->[$j] > $target;` [download] on the basis that a single comparison was less processing than the addition plus comparison in `if ($input->[$i] + $input->[$j] == $target) {` [download] I thought that was a handy logic short-circuit; however, I hadn't taken into account negative numbers. I've removed that line and the `INNER` label: all tests now pass. "Also - kcott's code assumes and takes advantage of the input being sorted - input order is NOT specified in the problem definition." I don't know where you got that idea from. I neither made that assumption nor wrote any code taking advantage of such sorting. Note `[[3,2,4], 6, [1,2]]` which has unsorted input. — Ken	[reply] [d/l] [select]
Re^2: LeetCode Problem #1 - Two Sum - Improve and/or discuss. by ikegami (Patriarch) on Jan 25, 2022 at 14:40 UTC
This is O(N) instead of O(N^2), so it will scale better.	[reply]