FastPrepCourse Order and Cycle
Problems/Course Order and Cycle

Course Order and Cycle

Amazon logoAmazon● HardFULLTIMEPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: Reports describe prerequisite execution order, cycle identification, and a changed-task rerun follow-up. Canonical sorted traversal, filtered full ordering, global cycle scope, and runner bounds are practice conventions. Conservative editorial estimate of source-family task coverage: about 85%.

There are numCourses courses numbered from 0 through numCourses - 1. Each row [course, prerequisite] means the prerequisite must be completed before the course.

Some course tasks have changed. changedCourses lists their IDs. Rerun each changed course and every course that directly or indirectly depends on a changed course; unchanged prerequisites may reuse their previous results.

For this exercise, assume the dependency graph is checked globally. Return a two-row result [order, cycle]:

  • For an acyclic graph, first construct the lexicographically smallest topological order of all courses. Return only affected courses, preserving their order in that full ordering, and an empty cycle. An empty changed set needs no reruns.
  • If the graph contains a cycle, return an empty order and one directed cycle in cycle. Do not repeat the first course at the end. This global cycle result applies even when the cycle lies outside the affected set.

To make cycle selection deterministic, inspect starting courses in increasing order and each course's outgoing neighbors in increasing order. Return the active-path segment closed by the first back edge encountered.

Mark every course as changed to solve the original full execution-order task. The filtered full ordering is one deterministic valid rerun order; it need not be the lexicographically smallest order of the affected subgraph alone.

Function

analyzeCourses(numCourses: int, prerequisites: int[][], changedCourses: int[]) → int[][]

Examples

Example 1

numCourses = 4prerequisites = [[1,0],[2,0],[3,1],[3,2]]changedCourses = [0,1,2,3]return = [[0,1,2,3],[]]

Course 0 is first. Courses 1 and 2 then become available, and the smaller course is chosen first.

Example 2

numCourses = 3prerequisites = [[1,0],[2,1],[0,2]]changedCourses = [0,1,2]return = [[],[0,1,2]]

The directed edges form 0 -> 1 -> 2 -> 0, so no topological order exists.

Example 3

numCourses = 6prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3]]changedCourses = [1]return = [[1,3,4],[]]

Course 1 changed. Courses 3 and 4 depend on it, including the indirect dependency. Courses 0 and 2 reuse their results and course 5 is unrelated.

Constraints

  • 1 <= numCourses <= 10^5.
  • 0 <= prerequisites.length <= 2 * 10^5.
  • Every prerequisite row contains two distinct valid course numbers.
  • No prerequisite edge appears more than once.
  • For this exercise, assume 0 <= changedCourses.length <= numCourses, and changed course IDs are unique valid course numbers.

More Amazon problems

  • Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
See Amazon hiring insights
Saved
class Solution {
    public int[][] analyzeCourses(int numCourses, int[][] prerequisites, int[] changedCourses) {
        // Write your code here.
    }
}
Checking account…