My solution to a Leetcode problem

readme.md

Download this gist as a zip, then install and run as follows:

npm install
npx ts-node coursePrerequisites.ts

coursePrerequisites.ts

// Taken from https://leetcode.com/problems/course-schedule/

/* 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 true if you can finish all courses. Otherwise,
// return false.
//
//
// Example 1:
//
// 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.
//
// Example 2:
//
// 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: */

// 1 <= numCourses <= 105
// 0 <= prerequisites.length <= 5000
// prerequisites[i].length == 2
// 0 <= a_i, b_i < numCourses
// All the pairs prerequisites[i] are unique.

/* Example solution */

// This is a graph problem. Specifically, we want to find cycles in a directed graph.
// The usual algorithm for this is to do a series of depth-first traversals.
// https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

/**
 * An adjacency list representation of a graph. Key is the graph node, value is
 * list of nodes it's connected to.
 */
type AdjacencyList = ReadonlyMap<number, ReadonlyArray<number>>;

/**
 * Converts the problem inputs into an Adjacency List graph representation. This
 * is a "sparse" adjacency list – a node may not be present if it has no edges.
 * That is fine for the needs of this problem, but is not always okay.
 */
export function makeGraph(prereqs: [number, number][]): AdjacencyList {
  const graph = new Map<number, number[]>();

  // Add each edge to the adjacency list. For this problem, since we just care
  // about finding cycles, we could invert the direction of all the edges and
  // still get the same result, so we don't have to be careful about which
  // direction the prereq edges are pointing (as long as it's consistent).
  for (const [course, prereq] of prereqs) {
    const edges = graph.get(course) || [];
    edges.push(prereq);
    graph.set(course, edges);
  }

  return graph;
}

/**
 * Color each node as it's traversed, using the scheme described here:
 * https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
 *
 * - black: this node and its descendants are fully traversed
 * - white (undefined): not yet visited
 * - grey: node has been visited, but its descendants are still being traversed
 */
type NodeColorings = Map<number, 'grey' | 'black' | undefined>;

/**
 * Determines if the given graph contains a cycle. Uses the following algorithm:
 *
 * Performs recursive depth-first traversals of the subtrees of the graph,
 * starting at each node, stopping early when one of the following conditions is
 * met:
 *
 * - Reaches a parent node (grey). This indicates a cycle.
 * - Reaches a node already seen from a prior traversal (black). At this point,
 *   we can stop this traversal because everything after that point has already
 *   been traversed, and any cycles downstream of that node would already have
 *   been caught.
 *
 * @returns true if a cycle was found, false otherwise
 */
export function doesGraphContainCycles(graph: AdjacencyList): boolean {
  const nodeColorings: NodeColorings = new Map();

  for (const startNode of graph.keys()) {
    const hasCycle = traverseDepthFirst({
      startNode,
      graph,
      nodeColorings,
    });

    if (hasCycle) {
      return true;
    }
  }

  // No cycle was found after traversing the entire graph
  return false;
}

/**
 * Visits each node in the graph that can be reached from the start node and
 * adds all such nodes to `seenInThisTree` as they are visited.
 *
 * @returns true if a cycle was found in this tree, false if the traversal was
 * completed with no cycles found.
 */
function traverseDepthFirst(params: {
  startNode: number;
  graph: AdjacencyList;
  nodeColorings: NodeColorings;
}): boolean {
  const { startNode, graph, nodeColorings } = params;

  // Base case 1: If this node is black, we've already processed its entire
  // subtree, so there's no more work to do.
  if (nodeColorings.get(startNode) === 'black') {
    return false;
  }

  // Base case 2: If this node is grey, it means there's a cycle.
  if (nodeColorings.get(startNode) === 'grey') {
    return true;
  }

  // Action: Color the node grey when we first visit it, but haven't yet
  // traversed its descendants
  nodeColorings.set(startNode, 'grey');

  // Recursive step: call this function again on each successive node
  const adjacentNodes = graph.get(startNode) ?? [];
  for (const adjacentNode of adjacentNodes) {
    const hasCycle = traverseDepthFirst({
      startNode: adjacentNode,
      graph,
      nodeColorings,
    });

    // Return: If we've reached a definitive result in a recursive step, keep
    // passing it up the call stack.
    if (hasCycle) {
      return true;
    }
  }

  // If there was no cycle found in the subtree, we've now fully traversed this
  // node, so color it to black.
  nodeColorings.set(startNode, 'black');
  return false;
}

/* Test cases */

/**
 * We can take the courses if no cycles were found in the graph.
 * In this solution, `numCourses` isn't actually used, so we ignore it.
 */
const consoleColors = require('colors');
function canTakeCourses(prereqs: [number, number][], expectedValue: boolean) {
  console.log(prereqs);
  const graph = makeGraph(prereqs);
  const canTakeCourses = !doesGraphContainCycles(graph);

  const logMessage = `Expected ${expectedValue}, got ${canTakeCourses}`;
  if (expectedValue === canTakeCourses) {
    console.log(consoleColors.green(logMessage));
  } else {
    console.log(consoleColors.red(logMessage));
  }
}

canTakeCourses([[1, 0]], true);
canTakeCourses(
  [
    [1, 0],
    [0, 1],
  ],
  false
);
canTakeCourses(
  [
    [1, 2],
    [1, 3],
    [2, 3],
    [2, 4],
    [2, 5],
    [5, 6],
    [7, 2],
  ],
  true
);
canTakeCourses(
  [
    [1, 2],
    [1, 3],
    [2, 3],
    [2, 4],
    [2, 5],
    [5, 6],
    [6, 7],
    [7, 2],
  ],
  false
);

package.json

{
  "dependencies": {
    "@types/node": "^14.14.34",
    "colors": "^1.4.0",
    "ts-node": "^9.1.1",
    "typescript": "^4.2.3"
  }
}

tsconfig.json

{
  "compilerOptions": {
    "target": "ES6"
  }
}