Two line brute force, Three line hash approach (Python, code golf)


  • 0

    This is in reply to Accepted Python Solution 4 lines. I wanted to take you up on a game of code golf ;) although my use of generator expressions may be considered less readable.

    Brute Force in 2 lines, O(n^2) time, O(1) space:
    (Edited first solution thanks to advice from StefanPochmann!)

    def twoSum(s,n,t):
      return [[i,n.index(t-x)] for i,x in enumerate(n) if t-x in n[:i]][0]
    

    Hash approach in 3 lines, O(n) time and space (two passes):

    def twoSum(self, xs, sum):
      d = {x:i for i,x in enumerate(xs)}
      return next([i,d[sum-x]] for i,x in enumerate(xs) if sum-x in d and i!=d[sum-x])
    

    Note the dict comprehensions [1] as well. This is super handy in interviews and works similarly for sets (omit the : symbol).

    [1] PEP uses "expression" and "comprehension" interchangeably in this context, as they are (transitively, via other languages) inspired by "set comprehensions" in mathematics.


  • 1

    For code golf, you're using far too many unnecessary characters :-)
    (spaces and variable names longer than one character)

    Your first version is wrong and doesn't get accepted. Update: got fixed.

    Shorter hash approach:

    def twoSum(_,n,t):
     j={x:i for i,x in enumerate(n)}
     return[[i,j[t-x]]for i,x in enumerate(n)if j.get(t-x)>i][0]
    

  • 0

    Aha, quite right :) I was only measuring lines at the time. And that bug! That's what I get for editing my code directly in the post without checking it.

    Thanks! I updated the first approach above, but left the other one as is so your shorter hash approach would still make sense.

    Oh, and cool use of j.get(...) instead of j[...]. I never thought to check what the difference was.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.