Union Find Python (49ms beats 100%)


  • 0
    # 38 / 38 test cases passed.
    # Status: Accepted
    # Runtime: 49 ms
    class Solution(object):
        def findRedundantConnection(self, edges):     
            p = {} # parents
            def find(x):
                return x if p[x] == x else find(p[x])
            def init(x):
                if x not in p: p[x] = x
            for e in edges:
                map(init, e)
                x, y = map(find, e)
                if x == y:  return e
                p[y] = x
                
    

  • 0
    3

    @TianQ How do you know if your solution beats 100%? They haven't displayed the solution statistics...


  • 0

    @paulalexis58 0_1506276827074_Screen Shot 2017-09-24 at 11.13.29 AM.png


  • 0

    @TianQ Five bars of exactly 20%... That's clearly just from five submissions. And if you click on them to read them, you'll find they're all mine. They're from testing before the contest. And they favored simplicity over runtime efficiency, so it's not surprising that you're faster.

    Reminds me I need to be more careful with what I submit, now that it might become publicly visible :-)

    Btw, you could do p.setdefault(x, x) instead of if x not in p: p[x] = x. I think it's nicer, and it might be a little faster (since it doesn't need to hash and search the value twice).


  • 0
    3

    @TianQ Yes, for me it displayed "Sorry. We do not have enough accepted submissions to show runtime distribution chart." that's why I wondered.
    Anyways your code is nice and concise :)
    Thanks for sharing your solution.


  • 0

    @paulalexis58 Make sense. :)


  • 0

    @StefanPochmann lol that makes sense. Also, thank you for your suggestion.


  • 0
    L
    This post is deleted!

Log in to reply
 

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