Course Schedule: Day 29 of May Leetcode Challenge

My solution to Course Schedule, the question for Day 29 of the May Leetcoding Challenge challenge

Why Take The Challenge?

Leetcode is a platform to practice and improve your coding skills, targetting data structures, time and space complexity. It teaches you to translate problem statement into code. It is a great resource to prepare for technical interviews. It has a lot of interesting and helpful coding questions that can help you be better prepared for an interview. You can pass the technical interviews at elite tech companies like Facebook, Amazon, Apple, Netflix, and Google. LeetCode questions are often asked during interviews at these companies, some more than at others.

‘Think twice, code once’

Pre-requisites

  • Understanding of atleast one programming language
  • Basic knowledge of data structures

Course Schedule: Problem Definition

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Examples:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
            To take course 1 you should have finished course 0. So it is possible.

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
            To take course 1 you should have finished course 0, and to take course 0 you should
            also have finished course 1. So it is impossible.

Constraints:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites. 1 <= numCourses <= 10^5

Hint #1

This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

Hint #2

Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

Hint #3

Topological sort could also be done via BFS.

Approach

Making use of hint 2, I carried out topological sort via DFS.

Solution


    class Solution:
        def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
            edge=defaultdict(list)
            for p in prerequisites:
                edge[p[0]].append(p[1]) # from:to 

            for k in range(numCourses): # for each start point
                stack=[k]
                visit=set()
                while stack:
                    node=stack.pop(0)
                    if visit and node==k:     # ignore the first start node
                        return False
                    if node not in visit:
                        visit.add(node)
                        stack+=edge[node]
            return True

while(!(succeed=try()));

Submission Stats

46 / 46 test cases passed.
Status: Accepted
Runtime: 572 ms
Memory Usage: 15.2 MB

My runtime beat 15.67 % of python3 submissions

If you are stuck at any point or have any doubts, drop a message here

Published by in Competitive Coding and tagged Algorithms, Competitive Coding, Data Structures, Python and search using 470 words.

comments powered by Disqus