in reply to 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.

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
[reply]

In Section Seekers of Perl Wisdom