Suggestion if you meet TLE


  • 0
    O

    Although it's quite embarrassing, my code took about 1800 ms at the first time.
    My status didn't even show on the distribution graph!

    If you meet similar situations, and you can't figure it out,
    I think you can ask yourself a question:

    What is the next class to finish, and how do I trace with it?

    My mistakes (1824 ms):

    • I maintained a list to record number of prerequisites for each class.
    • Everytime I finished a class, I needed to find a class without prerequisite...
      ==> I gain the time to sort this list everytime I finished a class.

    Answer (120 ms):

    • Just keep a zeroPreSet to store the class that doesn't have any prerequisite.

    • zeroPreSet could be initialized when you load the prerequisites into your structure.

    • Update zeroPreSet every time you finish a class. (If this A is the only prerequisite for B, you can simply add A into zeroPreSet)

    Sample Code in Python:

    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {integer[]}
    def findOrder(self, numCourses, prerequisites):
        if not prerequisites:
            return [i for i in range(numCourses)]
        zeroPre = set([i for i in range(numCourses)])
        table = collections.defaultdict(set)
        rtable = collections.defaultdict(set)
        for cls, pre in prerequisites:
            table[cls].add(pre)
            rtable[pre].add(cls)
            zeroPre.discard(cls)
        doneN, ans = 0, [0]*numCourses
        while zeroPre:
            doneIdx = zeroPre.pop()
            ans[doneN], doneN = doneIdx, doneN+1
            if doneN == numCourses:
                return ans
            if doneIdx in rtable:
                for cls in rtable[doneIdx]:
                    table[cls].discard(doneIdx)
                    if not table[cls]:
                        zeroPre.add(cls)
        return []

Log in to reply
 

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