Why I got TLE with my Java solution?


  • 0
    S

    My Java solution was inspired by this post: https://discuss.leetcode.com/topic/13854/easy-bfs-topological-sort-java

    When I copy - paste the solution shared in the post, it passes:

    public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];
    
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }
    
    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
    

    }

    However, if I exchange the rows and columns in the matrix (and no other changes) I got TLE:

       public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;
        int[][] matrix = new int[n][n];
        int[] inDegree = new int[n];
        for(int i=0; i<prerequisites.length; i++){
            int ready = prerequisites[i][0];
            int pre = prerequisites[i][1];
            if(matrix[ready][pre] == 0)
                inDegree[ready]++;
            matrix[ready][pre] = 1;
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i<n; i++){
            if(inDegree[i]==0)
                queue.offer(i);
        }
        int total = 0;
        while(!queue.isEmpty()){
            int course = queue.poll();
            total++;
            for(int i=0; i<n; i++){
                if(matrix[i][course] == 1){
                    matrix[i][course] = 0;
                    if(--inDegree[i] == 0)
                        queue.offer(i);
                }    
            }
        }
        return total == n;
    }
    

    Can someone explain me why?


Log in to reply
 

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