Python BFS


  • 20
    def findValueMostElement(self, root):
        maxes = []
        row = [root]
        while any(row):
            maxes.append(max(node.val for node in row))
            row = [kid for node in row for kid in (node.left, node.right) if kid]
        return maxes

  • 1

    @StefanPochmann
    Any to deal will the case [None] is brilliant.
    Could give some explanation on the code:

    [kid for node in row for kid in (node.left, node.right) if kid]
    

    I have never used two for embedded.


  • 4

    @lee215 I'll try to explain this part. Please tell me if I'm wrong.

    row = [kid for node in row for kid in (node.left, node.right) if kid]
    

    is equal to:

    row = [a,b,c,d...]
    xxx = []
    for node in row:
        for kid in (node.left, node.right):
            if kid:
                xxx += kid,
    row = xxx
    

    Note that @StefanPochmann keep updates the row list again and again. How great this is!


  • 0

    excellent and elegant


  • 0
    S

    Hi Stefan,
    Thank you for a nice solution.
    I am always surprised how you write the most concise solution.
    Reading your solution is becoming an art form for me :D
    Thank you.


  • 0
    L

    @StefanPochmann Just curious, is the max in "max(node.val for node in row)" taking the max at each sequential step or is it taking the max after the for loop is completed? Given that you don't need that extra for loop for calculating the max since you already go through each node in the row in the other for loop.


  • 0

    @livelearn said in Python BFS:

    taking the max after the for loop is completed

    Not sure what you mean with that...


  • 0
    L

    @StefanPochmann For example, is it doing this:

    maxx=inf("-inf")
    for i in a:
        maxx=max(i,maxx)
    or 
    for i in a
        tmp.append(i)
    max(tmp)

  • 0

    @livelearn It's neither of those. It looks more like your second version, as I call max just once and I do give it only one thing. But it really is more like your first version. That one thing I give to max is a generator, which provides the values one by one on demand. And then max will, under the hood, do something like your first version.


  • 0
    P

    @StefanPochmann Such condensed code, brilliant. The max per row and the row can be computed in the same pass to make the solution even quicker. I used the same BFS idea but computed max per row and rows in same pass.

    Here's my solution: https://discuss.leetcode.com/topic/92079/simple-python-bfs-beats-99-83-65ms


  • 0

    @pramttl said in Python BFS:

    to make the solution even quicker

    Doesn't look quicker to me. Where are your statistics?

    I did some myself now, renaming our function and adding this one:

    def largestValues(self, root):
        for _ in range(100):
            answer = self._largestValues(root)
        return answer
    

    Then I alternately submitted our solutions three times. The times (in ms):

    mine yours
    705   736
    696   779
    815   802
    

    They look very similar, with mine looking a bit quicker. I doubt you tested this properly or at all.


  • 0
    P

    @StefanPochmann In your solution there are 2 passes over the row, one to compute maximum and one to compute kids. Logically, wouldn't it be quicker to use a single pass to compute max and child row ?

    I got 65 ms on Leetcode on submitting my solution (shared snapshot in comments section of my solution) and that's why I claimed it is quicker. Being new to Leetcode, wasn't aware that the runtime can vary so much on multiple submissions. (probably because of smaller test cases). I just wanted to highlight that single pass to compute row max and next row could be quicker if the tree is very large with several elements per row. If I am wrong, let me know ?


  • 0

    @pramttl Your single pass does more than each of my two passes. It does the same as both of mine together. Granted, the pure iteration is done twice in mine, but yours spends more time on each item. You're calling max for each node (I only call it once per row) and you look up and call curr_level_nodes.append for each node. List comprehensions do that more efficiently. Compare what happens in each iteration in loop+append vs list comprehension:

    >>> def f():
    	ans = []
    	for x in X:
    		ans.append(x)
    	return ans
    
    >>> import dis
    >>> dis.dis(f)
      3           0 BUILD_LIST               0
                  3 STORE_FAST               0 (ans)
    
      4           6 SETUP_LOOP              27 (to 36)
                  9 LOAD_GLOBAL              0 (X)
                 12 GET_ITER            
            >>   13 FOR_ITER                19 (to 35)
                 16 STORE_FAST               1 (x)
    
      5          19 LOAD_FAST                0 (ans)
                 22 LOAD_ATTR                1 (append)
                 25 LOAD_FAST                1 (x)
                 28 CALL_FUNCTION            1
                 31 POP_TOP             
                 32 JUMP_ABSOLUTE           13
            >>   35 POP_BLOCK           
    
      6     >>   36 LOAD_FAST                0 (ans)
                 39 RETURN_VALUE        
    >>> def g():
    	return [x for x in X]
    
    >>> dis.dis(g)
      3           0 BUILD_LIST               0
                  3 LOAD_GLOBAL              0 (X)
                  6 GET_ITER            
            >>    7 FOR_ITER                12 (to 22)
                 10 STORE_FAST               0 (x)
                 13 LOAD_FAST                0 (x)
                 16 LIST_APPEND              2
                 19 JUMP_ABSOLUTE            7
            >>   22 RETURN_VALUE        
    

    What the list comprehension does with a simple LIST_APPEND, the loop+append does with LOAD_FAST(ans), LOAD_ATTR(append), CALL_FUNCTION and POP_TOP.

    I btw just tested a bit more and got very unstable times, from about 700 ms to about 1400 ms. I guess the server is under more load right now. Maybe because the Americans are awake now. Ideally one would extract all test cases and do local testing without other things on the PC going on, and repeat the tests even more often than just 100 times and do it more often than just three times. Though then you'd compare it on your PC and that might not be perfectly representative for running it on LeetCode (though that doesn't need to be bad). Anyway, it's a bit too much work for me to bother doing that now :-P


Log in to reply
 

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