Python: 2-5 lines, O(n) time, O(1) space


  • 3
    def thirdMax(self, nums):
        l = [float('-inf')] * 3
        for n in nums:
            if n > l[0] and n not in l:
                heapq.heappushpop(l, n)
        return l[0] if l[0] != float('-inf') else max(l)
    

    A slightly shorter but uglier version based on the same concept is:

    def thirdMax(self, nums):
        l = [float('-inf')] * 3
        [heapq.heappushpop(l, n) for n in nums if n > l[0] and n not in l]
        return l[0] if l[0] != float('-inf') else max(l)
    

    Although I'm not sure whether the second version is still O(1) space. Does anyone know whether the Python interpreter will create the whole list comprehension in memory even though it is not being assigned anywhere?

    Update: two line solution by @StefanPochmann below.


  • 0

    I don't understand why/when heapify would be needed, can you explain more?

    "Optimizing away" an unused list comprehension like that doesn't feel to me like something CPython would do. I think if asked for that, they'd reply "Are you kidding me? You want us to optimize something because you did it wrong?" :-). Anyway, I'd say just test it, for example add [x for x in xrange(10**7)] to your solution and you'll see it gets Memory Limit Exceeded.


  • 1

    You are right about the heapify comment in my code. I originally overlooked the part of the problem stating that equal elements should be ignored for counting and had a different solution. I later changed the code but forgot to remove the comment. I'm removing it now.

    And you're right again about the list comprehension being created, so only my first solution is O(1) space.

    Just to keep the title of the thread true, here is a 3-line solution in O(n) time & O(1) space, but it just keeps getting uglier :-D. Anyone reading is seriously advised not to use the following concept! Just use a couple more lines and keep the code clean:

    def thirdMax(self, nums):
        l = [float('-inf')] * 3
        for _ in (heapq.heappushpop(l, n) for n in nums if n > l[0] and n not in l): pass
        return l[0] if l[0] != float('-inf') else max(l)
    

  • 1

    @dalwise Hacking further:

    def thirdMax(self, nums):
        l = [None] * 3
        for n in nums: l[0] < n not in l < heapq.heappushpop(l, n)
        return l[0] if l[0] > None else max(l)

  • 1

    @StefanPochmann your code is instructive as always!

    In case anyone else is like me and doesn't immediately see how Stefan's second line is evaluated, note that it is roughly equivalent to:

    for n in nums: (l[0] < n) and (n not in l) and (l < heapq.heappushpop(l, n))
    

    The result of the last comparison is not used, so the following also produces a valid result:

    for n in nums: (l[0] < n) and (n not in l) and (l > heapq.heappushpop(l, n))
    

    And this too:

    for n in nums: (l[0] < n) and (n not in l) and heapq.heappushpop(l, n)
    

    For more info refresh this and this.

    Using None instead of float('-inf') makes the code slightly shorter, but also makes it no longer compatible with Python3, since in Python3 None cannot be compared with an int. Stefan's code also would not work in Python3 since he compares a list with the result of a function that returns a number.

    I think that the following is the shortest concept that works in both Python2 & Python3 while still being O(n) time & O(1) space:

    def thirdMax(nums):
        l = [float('-inf')] * 3
        for n in nums: l[0] < n not in l and heapq.heappushpop(l, n)
        return l[0] if l[0] > float('-inf') else max(l)
    

  • 1

    @dalwise Good analysis of my hacks :-). You could use the shorter -9**99 in instead of float('-inf'), because we actually get signed 32-bit ints, though I like float('-inf') better.

    Anyway, still shorter:

    def thirdMax(self, nums):
        l = []
        for n in nums: l = sorted(set(l) | {n})[-3:]
        return l[len(l) / 3 - 1]
    

    Or:

    def thirdMax(self, nums):
        l = reduce(lambda l, n: sorted(set(l) | {n})[-3:], nums, [])
        return l[len(l) / 3 - 1]

  • 0

    @dalwise said in Python: 2-5 lines, O(n) time, O(1) space:

    I think that the following is the shortest concept that works in both Python2 & Python3 while still being O(n) time & O(1) space:

    def thirdMax(nums):
        l = [float('-inf')] * 3
        for n in nums: l[0] < n not in l and heapq.heappushpop(l, n)
        return l[0] if l[0] > float('-inf') else max(l)
    

    Always a good learning experience to be corrected :)


  • 0
    Y

    can you write some easy-to-understadn python code? I completely don't understand your code. What does heapq.heappushpop() mean by the way?


  • 0

    @YaoshuaiZhang said in Python: 2-5 lines, O(n) time, O(1) space:

    can you write some easy-to-understadn python code? I completely don't understand your code. What does heapq.heappushpop() mean by the way?

    Explained here


Log in to reply
 

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