18 lines HashMap Solution using Java


  • 0
    S

    I use hashmap to store the relationships. Whenever I find one course that is the prereq of other classes, I use hashmap to trace what course is the prereq for. If found out that these two are equivalent, then the result is gonna be false.

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int n = prerequisites.length;
            Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < n; i++) {
                    Integer cur = map.get(prerequisites[i][1]);
                    while(cur != null) {
                            if(cur == prerequisites[i][0]) {
                                    return false;
                            }
                            cur = map.get(cur);
                    }
                    map.put(prerequisites[i][0], prerequisites[i][1]);
            }
            return true;
            }
    }


Log in to reply
 

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