heapq.heappushpop clear solution for The Final Stone by juestr - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

heapq.heappushpop solution in Clear category for The Final Stone by juestr

from heapq import heapify, heappop, heappushpop

def final_stone(stones: list[int]) -> int:
    if not stones:
        return 0
    else:
        heap = [-s for s in stones]
        heapify(heap)
        largest = heappop(heap)    
        while heap:
            nextlargest = heappop(heap)
            largest = heappushpop(heap, largest - nextlargest)       
        return -largest

July 26, 2022

Comments:

kudinov.feodor on March 13, 2023, 11:21 a.m.
thought about heap, but ended with bisect search not to mangle signs I wonder which solution is more effective

juestr on March 13, 2023, 9:57 p.m.
I think using `insort_*` doesn't lead to a theoretically optimal solution, since it needs to shuffle half the target array on average on each call. That's O(n) per call, O(n**2) total, vs O(n * log n) with a heap. The problem really isn't `bisect` or even `insort`, it's that `list` has O(n) insertion. But `list` is highly optimized, so it may not matter in practice.

The Game is Worth it!

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!