Tasks

Topological Sort

Index	Task Name	Task Number	Difficulty	Link
1	Course Schedule	207	Medium	Link
2	Course Schedule II	210	Medium	Link
3	Alien Dictionary	269	Hard	Link
4	Sequence Reconstruction	444	Medium	Link
5	Minimum Height Trees	310	Medium	Link
6	Parallel Courses	1136	Hard	Link
7	Course Schedule III	630	Hard	Link
8	Reconstruct Itinerary	332	Medium	Link
9	Find the Town Judge	997	Easy	Link
10	All Nodes Distance K in Binary Tree	863	Medium	Link
11	Find All Possible Recipes from Given Supplies	2115	Medium	Link

// 207. Course Schedule 

// Time: O(E + numCourses), where E is the number of prerequisites.
// Space: O(numCourses).
var canFinish = function(numCourses, prerequisites) {
    // Create an array 'inDegrees' to keep track of the in-degrees for each course
    const inDegrees = Array(numCourses).fill(0);

    // Iterate through 'prerequisites' and increment in-degrees 
    // for courses that have prerequisites
    for (const [v] of prerequisites) {
        inDegrees[v]++;
    }

    // Initialize a queue 'q' to store courses with no prerequisites
    const q = [];

    // Populate the queue with courses that have no prerequisites (in-degrees equal to 0)
    for (let i = 0; i < inDegrees.length; i++) {
        const degree = inDegrees[i];
        if (degree === 0) q.push(i);
    }

    // Perform topological sorting using a BFS approach
    while (q.length) {
        // Dequeue a course with no prerequisites
        const u0 = q.shift();

        // Decrement 'numCourses' to keep track of the courses taken
        numCourses--;

        // Update in-degrees for courses that depend on the course 'u0'
        for (const [v, u] of prerequisites) {
            if (u === u0) {
                inDegrees[v]--;

                // If the in-degree becomes 0, add it to the queue as it can be taken now
                if (inDegrees[v] === 0) q.push(v);
            }
        }
    }

    // If all courses can be taken - numCourses is 0
    return numCourses === 0;
};

/*
Topological Sort
-----------------------------
1. Collect in-degrees for every course.
2. Init queue with 0-in-degree courses.
3. Dequeue step-by-step to build the result.
-----------------------------
Time: O(E + numCourses)
Space: O(numCourses)
*/

// 210. Course Schedule II

// Time: O(E + numCourses), where E is the number of prerequisites.
// Space: O(numCourses).
var findOrder = function(numCourses, prerequisites) {
    // Create an array 'inDegrees' to keep track of the in-degrees for each course
    const inDegrees = Array(numCourses).fill(0);

    // Iterate through 'prerequisites' and increment in-degrees 
    // for courses that have prerequisites
    for (const [v] of prerequisites) {
        inDegrees[v]++;
    }

    // Initialize a queue 'q' to store courses with no prerequisites
    const q = [];

    // Populate the queue with courses that have no prerequisites (in-degrees equal to 0)
    for (let i = 0; i < inDegrees.length; i++) {
        const degree = inDegrees[i];
        if (degree === 0) q.push(i);
    }

    // Initialize an array 'res' to store the topological order
    const res = [];

    // Perform topological sorting using a BFS approach
    while (q.length) {
        // Dequeue a course with no prerequisites
        const u0 = q.shift();

        // Decrement 'numCourses' to keep track of the courses taken
        numCourses--;

        // Add the course to the result (topological order)
        res.push(u0);

        // Update in-degrees for courses that depend on the course 'u0'
        for (const [v, u] of prerequisites) {
            if (u === u0) {
                inDegrees[v]--;

                // If the in-degree becomes 0, add it to the queue as it can be taken now
                if (inDegrees[v] === 0) q.push(v);
            }
        }
    }

    // If all courses can be taken (numCourses is 0), return the topological order; 
    // otherwise, return an empty array
    return numCourses === 0 ? res : [];
};

/*
Topological Sort
-----------------------------
1. Collect in-degrees for every course.
2. Init queue with 0-in-degree courses.
3. Dequeue step-by-step to build the result.
-----------------------------
Time: O(E + numCourses)
Space: O(numCourses)
*/

// 269. Alien Dictionary

// Time: O(C + N), where C is the total number of characters 
// in the words, N is the number of words.

// Space: O(V), where V is the number of unique characters in the input.
function alienOrder(words) {
  // Create a graph to represent the order of characters
  const graph = new Map();
  
  // Create an in-degree map to count incoming edges for each character
  const inDegree = new Map();
  
  // Initialize the graph and in-degree map with characters
  for (const word of words) {
    for (const char of word) {
      graph.set(char, new Set());
      inDegree.set(char, 0);
    }
  }

  // Build the graph and in-degree map based on the given words
  for (let i = 0; i < words.length - 1; i++) {
    const word1 = words[i];
    const word2 = words[i + 1];
    let found = false;

    for (let j = 0; j < Math.min(word1.length, word2.length); j++) {
      const char1 = word1[j];
      const char2 = word2[j];

      if (char1 !== char2) {
        if (!graph.get(char1).has(char2)) {
          graph.get(char1).add(char2);
          inDegree.set(char2, inDegree.get(char2) + 1);
        }
        found = true;
        break;
      }
    }

    if (!found && word1.length > word2.length) {
      return '';
    }
  }

  // Perform topological sorting using a queue
  const queue = [];
  for (const [char, degree] of inDegree) {
    if (degree === 0) {
      queue.push(char);
    }
  }

  const result = [];
  while (queue.length > 0) {
    const char = queue.shift();
    result.push(char);

    for (const neighbor of graph.get(char)) {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);
      if (inDegree.get(neighbor) === 0) {
        queue.push(neighbor);
      }
    }
  }

  // Check if a valid ordering is possible
  if (result.length !== inDegree.size) {
    return '';
  }

  // Convert the result array to a string and return the alien dictionary order
  return result.join('');
}

// Verifying an Alien Dictionary

// Time: O(m) , where m is the total number of letters in the list of words.
// Space: O(1)
export function verifyAlienDictionary(words, order) {
  // If there's only one word in the array, it's always in order
  if (words.length == 1) {
    return true;
  }

  // Create a map to store the order of characters based on the given 'order' string
  let orderMap = {};

  // Populate the orderMap with character-to-index mappings
  for (let i = 0; i < order.length; i++) {
    let val = order[i];
    orderMap[val] = i;
  }

  // Iterate through adjacent pairs of words
  for (let i = 0; i < words.length - 1; i++) {
    // Iterate through characters in the current word
    for (let j = 0; j < words[i].length; j++) {
      // Check if the index 'j' exceeds the length of the next word
      if (j >= words[i + 1].length) {
        // If it does, the current word is longer than the next, so it's not in order
        return false;
      }

      // Compare characters at the same position in the two words
      if (words[i][j] != words[i + 1][j]) {
        // If they are different, check their order based on the orderMap
        if (orderMap[words[i][j]] > orderMap[words[i + 1][j]]) {
          // If the current character is out of order, return false
          return false;
        }
        // If the order is correct, move on to the next word
        break;
      }
    }
  }

  // If all adjacent word pairs are in order, return true
  return true;
}

// 2115. Find All Possible Recipes from Given Supplies

// Time: O(n * m), where n recipes and m ingredients.
// Space: O(n).
var findAllRecipes = function(recipes, ingredients, supplies) {
    // Initialize graph to represent dependencies between ingredients and recipes
    let graph = {};
    // Initialize in-degree to track how many dependencies each recipe has
    let inDegree = {};

    // Build the graph and in-degree information
    for (let i = 0; i < recipes.length; i++) {
        // Set the in-degree of the recipe to the number of required ingredients
        inDegree[recipes[i]] = ingredients[i].length;

        for (const parent of ingredients[i]) {
            // Initialize graph ingredient.
            if (!graph[parent]) {
                graph[parent] = [];
            }
            // Add the recipe as a dependent of the ingredient
            graph[parent].push(recipes[i]);
        }
    }

    // Initialize an array to store the recipes that can be created
    let result = [];
    // Initialize a queue with the initial supplies
    let queue = supplies.slice();

    // Perform a breadth-first search starting from the initial supplies
    while (queue.length) {
        // Dequeue a supply
        const supply = queue.shift();

        // If the supply is a recipe, it can be created
        if (recipes.includes(supply)) {
            result.push(supply);
        }

        // Check if there are recipes that depend on this supply
        if (graph[supply]?.length) {
            // Process recipes that depend on the supply
            for (const recipe of graph[supply]) {
                inDegree[recipe] -= 1; // Decrement the in-degree of the recipe

                // If the in-degree becomes 0, the recipe can be created, so add it to the queue
                if (inDegree[recipe] === 0) {
                    queue.push(recipe);
                }
            }
        }
    }

    // Return the list of recipes that can be created
    return result;
};