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

I believe this runs in O(n) time. But that's on the presumption that the input list of numbers is already sorted. If it's not, then this solution would have to add a sorting step, which will make it O(n log n).

sub TwoSum
{
    my( $target, @nums ) = @_;
    # assumption: @nums are already sorted.
    # caveat: the nums in the list might not be uniq!!!
    
    my %num; @num{@nums} = (); # for existence tests.

    for my $i2 ( reverse( 1 .. $#nums ) )
    {
        my $d = $target - $nums[$i2];
        if ( exists $num{$d} )
        { # gotta find the _first_ occurrence of this number in the li
+st:
            my($i1) = grep { $nums[$_] == $d } 0 .. $i2-1;
            return( $i1, $i2 );
        }
    }

    die
}
[download]

I reckon we are the only monastery ever to have a dungeon staffed with 16,000 zombies.

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 18:45 UTC
G'day jdporter, I liked the general thinking behind this; however, I see two issues. "`# assumption: @nums are already sorted.`" There is no requirement for the input list to be sorted. As an example, see "1. Two Sum" Example 2: `Input: nums = [3,2,4], target = 6 Output: [1,2]` [download] If you did "add a sorting step", you could potentially change the result: `Input: nums = [2,3,4], target = 6 Output: [0,2]` [download] "`# caveat: the nums in the list might not be uniq!!!`" Again, there's no requirement for this uniqueness. See Example 3: `Input: nums = [3,3], target = 6 Output: [0,1]` [download] As far as I can tell (by inspection) your code produces a correct result with this input. An input of `[3,1,1,1,3]` would produce a correct result: `[0,4]`. An input of `[3,3,3]` would be invalid from the outset, because there's more than one possible solution: `[0,1]`, `[0,2]` and `[1,2]` — whatever code you (or anyone) wrote would be immaterial for this input. — Ken	[reply] [d/l] [select]
Re^2: LeetCode Problem #1 - Two Sum - Improve and/or discuss. by LanX (Saint) on Jan 25, 2022 at 13:44 UTC
As already pointed out by kcott is the uniqueness of the solution guarantied. --> Re^8: LeetCode Problem #1 - Two Sum - Improve and/or discuss. Hence no need for greping. If the first occurrence was really required, I'd rather store it in the hash. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]


Clear questions and runnable code get the best and fastest answer
	PerlMonks