What is the time complexity of Course Schedule II?

The optimal solution has a time complexity of O(V+E).

What is the space complexity of Course Schedule II?

The space complexity is O(V+E).

What data structures are used to solve Course Schedule II?

This problem uses Depth-First Search, Breadth-First Search, Graph, Topological Sort. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Course Schedule II?

Insight 1: The problem can be modeled as a directed graph, where courses are nodes and prerequisites are directed edges. A valid course schedule corresponds to a topological sort of this graph. Insight 2: The presence of cycles in the graph indicates that it is impossible to complete all courses (a cyclic dependency).

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Course Schedule II - LeetCode 210 Solution

Q: Which companies ask LeetCode 210. Course Schedule II in interviews?

This problem is frequently asked at Anduril, Arista Networks, ByteDance, Citadel, Databricks and 18 more companies.

Course Schedule II - Complete Solution Guide

Course Schedule II is LeetCode problem 210, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1 . You are given an array prerequisites where prerequisites[i] = [a i , b i ] indicates that you must take course b i first if you want to take course a i . For example, the pair [0, 1] , indicates that to take course 0 you have to first take course 1 . Return the ordering of courses you should take to finish all courses . If there are many valid answers, return any of them. If it is impossible to finish al

Detailed Explanation

The problem asks us to find a valid order in which to take a set of courses, given dependencies between them. These dependencies are represented as pairs [course, prerequisite], meaning you must take 'prerequisite' before 'course'. The goal is to return a list of courses that can be taken in order to complete all courses. If it's impossible to finish all courses due to a cyclic dependency, return an empty array. 'numCourses' represents the total number of courses, labeled from 0 to numCourses - 1. 'prerequisites' is a list of lists where each inner list has two integers [course, prerequisite]. The output should be a list representing a valid order to take courses, or an empty list if no such order exists.

Solution Approach

The provided solution uses Kahn's algorithm (a Breadth-First Search (BFS) approach) to perform topological sorting. It calculates the in-degree of each course (number of prerequisites) and initializes a queue with all courses that have an in-degree of 0 (no prerequisites). It then iteratively removes courses from the queue, adds them to the topological order, and reduces the in-degree of their neighbors. If a neighbor's in-degree becomes 0, it's added to the queue. If the number of courses in the topological order equals the total number of courses, a valid order has been found. Otherwise, a cycle exists, and an empty array is returned.

Step-by-Step Algorithm

Step 1: Build the adjacency list representation of the graph from the 'prerequisites' list. Also, compute the in-degree of each course.
Step 2: Initialize a queue with all courses that have an in-degree of 0.
Step 3: While the queue is not empty, dequeue a course, add it to the 'topological_order' list.
Step 4: For each neighbor of the dequeued course, decrement its in-degree. If the neighbor's in-degree becomes 0, enqueue it.
Step 5: After the queue is empty, check if the size of the 'topological_order' list is equal to 'numCourses'. If it is, return the 'topological_order' list. Otherwise, return an empty list, indicating the presence of a cycle.

Key Insights

Insight 1: The problem can be modeled as a directed graph, where courses are nodes and prerequisites are directed edges. A valid course schedule corresponds to a topological sort of this graph.
Insight 2: The presence of cycles in the graph indicates that it is impossible to complete all courses (a cyclic dependency).
Insight 3: We can use Kahn's algorithm (using in-degrees and a queue) or Depth-First Search (DFS) to detect cycles and perform topological sorting.

Complexity Analysis

Time Complexity: O(V+E)

Space Complexity: O(V+E)

Topics

This problem involves: Depth-First Search, Breadth-First Search, Graph, Topological Sort.

Companies

Asked at: Anduril, Arista Networks, ByteDance, Citadel, Databricks, DoorDash, Intuit, Karat, Netflix, Nvidia, Oracle, PhonePe, Qualcomm, Remitly, Salesforce, Snap, Snowflake, Tesla, VMware, Walmart Labs, Workday, Zenefits, eBay.

Course Schedule II | LeetCode 210

Medium

Depth-First Search Breadth-First Search Graph Topological Sort

Time: O(V+E)Space: O(V+E)

Solution Code

Available in:

import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj_list = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj_list.add(new ArrayList<>());
        }

        int[] in_degree = new int[numCourses];

        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prereq = prerequisite[1];
            adj_list.get(prereq).add(course);
            in_degree[course]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in_degree[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> topological_order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int course = queue.poll();
            topological_order.add(course);

            for (int neighbor : adj_list.get(course)) {
                in_degree[neighbor]--;
                if (in_degree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        if (topological_order.size() == numCourses) {
            int[] result = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                result[i] = topological_order.get(i);
            }
            return result;
        } else {
            return new int[0];
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 210: Course Schedule II - Detailed explanation and solution approaches.

Topics

Depth-First Search Breadth-First Search Graph Topological Sort

Companies

AndurilArista NetworksByteDanceCitadelDatabricksDoorDashIntuitKarat

Stats

Difficulty:Medium

Languages:4

Companies:23

Problem #:210

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Build the adjacency list representation of the graph from the 'prerequisites' list. Also, compute the in-degree of each course.
2
Step 2: Initialize a queue with all courses that have an in-degree of 0.
3
Step 3: While the queue is not empty, dequeue a course, add it to the 'topological_order' list.
4
Step 4: For each neighbor of the dequeued course, decrement its in-degree. If the neighbor's in-degree becomes 0, enqueue it.
5
Step 5: After the queue is empty, check if the size of the 'topological_order' list is equal to 'numCourses'. If it is, return the 'topological_order' list. Otherwise, return an empty list, indicating the presence of a cycle.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(V+E)

💾

Space Complexity

O(V+E)

📝

Why?

The time complexity is determined by the graph traversal. Each course and each prerequisite relationship are processed a constant number of times. The space complexity is dictated by the storage required for the adjacency list, in-degree array, queue, and result array. The adjacency list representation directly relates to the number of edges (prerequisites), and the other structures are directly proportional to the number of courses.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

An alternative approach involves using DFS to detect cycles and perform topological sorting. We can maintain a 'visited' and 'recursionStack' set for each node. During DFS, if we encounter a node already in the 'recursionStack', we have detected a cycle. Otherwise, after visiting all neighbors of a node, we add it to the topological order (in reverse).

Time: O(V+E)Space: O(V+E)

Trade-offs: DFS can be slightly harder to implement correctly due to the need for cycle detection using recursion stack. While the time and space complexity is the same, the constant factors may differ slightly in practice. DFS might be slightly faster in some cases if the graph is very sparse and has a simple topological order. The BFS (Kahn's Algorithm) approach is often preferred as it's generally considered more intuitive to understand.

✨

Key Insights

1Insight 1: The problem can be modeled as a directed graph, where courses are nodes and prerequisites are directed edges. A valid course schedule corresponds to a topological sort of this graph.
2Insight 2: The presence of cycles in the graph indicates that it is impossible to complete all courses (a cyclic dependency).
3Insight 3: We can use Kahn's algorithm (using in-degrees and a queue) or Depth-First Search (DFS) to detect cycles and perform topological sorting.

📚

Key Terms Explained

For Students

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: Empty prerequisite list (no dependencies). In this case, the algorithm correctly initializes the queue with all courses, and the topological sort becomes simply the list of courses from 0 to numCourses-1.
Edge case 2: Cyclic dependencies (e.g., course A depends on B, and course B depends on A). The algorithm detects cycles because the 'topological_order' list will not contain all courses. The function then returns an empty array.
Edge case 3: A course with no outgoing edges (no other courses depend on it). This case is handled correctly because the in-degree calculation accurately reflects this, and the course will be added to the queue as needed.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to detect cycles in the graph. If cycles are not properly detected, the algorithm may return an incorrect ordering or crash due to infinite loops.

✗Common mistake 2: Incorrectly building the adjacency list. It's essential to understand the relationship between 'course' and 'prerequisite' to correctly represent the dependencies in the graph.

✗Common mistake 3: Forgetting to handle courses with no prerequisites. These courses must be added to the queue initially.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Task scheduling or dependency resolution in software projects. For example, determining the order in which to compile source code files based on their dependencies.

🏦Real-world scenario 2: Course scheduling in universities, ensuring that prerequisites are taken before more advanced courses.

🎮Real-world scenario 3: Dependency resolution in package managers (like apt, npm, pip). Software packages often depend on other packages, and the package manager needs to determine a valid installation order.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 1, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

❓

Frequently Asked Questions

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Course Schedule II"?

For this medium-level Depth-First Search problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether breadth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?