TLE in Python Solution


  • 4
    M

    I came up with the following python solution, which more or less is a translation from jinwu's Java solution:
    https://leetcode.com/discuss/54201/short-java-solution

    Although it works for small test cases, when the test case is extremely large, it hits the TLE. I believe the issue is that whenever we remove an element from the priority queue, we need to re-heapify the entire list in order to maintain its invariant, and it is O(n) to heapify the list.

    Does anyone know how to work around this issue?

    import heapq
    
    class Solution(object):
        def getSkyline(self, buildings):
            """
            :type buildings: List[List[int]]
            :rtype: List[List[int]]
            """
            points = []
            for b in buildings:
                points.append((b[0], -b[2]))
                points.append((b[1], b[2]))
            points.sort(key=lambda x: (x[0], x[1]))
            
            # prev stores the current height
            prev = 0
            pq = [0]
            results = []
            for p in points:
                if p[1] < 0:
                    heapq.heappush(pq, p[1])
                else:
                    if -p[1] in pq:
                        pq.remove(-p[1])
                        heapq.heapify(pq)
                
                current = -pq[0]
                if prev != current:
                    results.append((p[0], current))
                    prev = current
            return results

  • 4
    R

    check http://stackoverflow.com/questions/10162679/python-delete-element-from-heap

    if -p[1] in pq:
        pq.remove(-p[1])
        heapq.heapify(pq)
    

    can be converted to:

    if -p[1] in pq:
        i = pq.index(-p[1])
        pq[i] = pq[-1]
        pq.pop()
        if i < len(pq):
            heapq._siftup(pq, i)
            heapq._siftdown(pq, 0, i)
    

  • 0
    A
    This post is deleted!

  • 0

    removing not from top is very slow in heap which takes O(n) time. Maybe it's not the problem of heapify.


  • 1

    It's weird to call internal functions but it works...


  • 0
    Z

    This also works slightly better than above approach. 775ms.

    index = q.index(-i[1])
    while index > 0:
        up = (index + 1) / 2 - 1
        q[index] = q[up]
        index = up
    heapq.heappop(q)
    

    PS: heapify(q) taks longer time. Because it does some useless work.


Log in to reply
 

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