Optimize an Algorithm to take in a disliked string and Array of [Prereq, next_class] sub-arrays, outputs number of classes you can take before it

Question

The course we want to avoid is guaranteed somewhere in the list of courses and prerequisites. There will be no untakeable courses. There may be multiple courses with no prerequisites. The prompt is to create a function which takes in a course to avoid, and a list of courses and prerequisites. Returns how many courses we can take before the course we want to avoid. The disliked course should be in the list of the courses and prerequisites, guaranteed. The function returns how many courses we can take before the course we want to avoid.

I have wrote this algorithm by hand without any efficiencies. I was hoping someone could help me optimize it or guide me in modern javascript algorithmic best practices as it took me longer than usual to form a solution. In addition, if someone could help me calculate the Big O time complexity of what I have, in explaining why another solution is better, it would be much appreciated.

var disliked = "Linear Algebra";

var prereqs = [
  ["Calculus 1", "Calculus 2"],
  ["Calculus 2", "Linear Algebra"],
  ["Linear Algebra", "Discrete Math"],
  ["Discrete Math", "Analysis of Algorithms"],
  ["Algorithms", "Analysis of Algorithms"],
  ["Data Structures", "Algorithms"],
  ["Algorithms", "AI"],
  ["Calculus 1", "AI"],
  ["AI", "Computer Vision"],
  ["Algorithms", "Networks"],
  ["Algorithms", "Operating Systems"],
  ["Analysis of Algorithms", "Theory of CS"],
];

function countCourses(disliked, prereqs) {

  // [x] 1) Choose dislike: ie, alg
  //  for each array {
  //    if current array indice 0 === "alg" (ie, dislike)
  //      push its indice value 1 to new array, delete current array
  //  ex, uniques[] = [analysis, AI, NET, OS]
  //  new array:  [calc1, calc2], [calc2, lin alg],[lin alg, d math], [d math, analysis], [d. struct, alg]
  //              [calc1, AI], [AI, comp], [analysis, theory]
  //
  // O(N)
  let next_classes = [];
  for (let i = 0; i < prereqs.length; i++) {
    if (prereqs[i][0] === disliked) {
      next_classes.push(prereqs[i][1]);
      prereqs.splice(i, 1);
      i = i - 1;
    }
  }
  console.table(next_classes);
  console.table(prereqs);
  
  // For each next class requirement in the sequence (after disliked class)
  // Remove, add to impossible_classes as we cannot take them
    // impossible_courses[]:  [analysis, AI, net, OS]
  for(let i = 0; i < prereqs.length; i++) {
    for(let j = 0; j < next_classes.length; j++) {
      if (prereqs[i][0] === next_classes[j]) {
        next_classes.push(prereqs[i][1]);
        //prereqs.splice(i, 1);
        //j = i - 1;
      }
    }
    }
  console.table(next_classes);
  
  // 2) for each array {
  //    if current array indice 0 === [a unique value] (ie, value from [analysis, AI, net, OS])
  //      delete current array
  //      Effectively deletes classes after unique [analysis, AI, net, OS] in the sequence,
  //      which cannot also be taken
  //      ie, theory, comp
  for (let i = 0; i < prereqs.length; i++) {
    for (let j = 0; j < next_classes.length; j++) {
      if (prereqs[i][0] === next_classes[j]) {
        prereqs.splice(i, 1);
        i = 0;
      }
    }
  }

  // if nothing inside impossible_courses --> that means,
  // the course you dislike is a "final course", nothing comes after it
  // it contains only pre-requisites.
  if (next_classes.length === 0) {
    for (let i = 0; i < prereqs.length; i++) {
      // find the disliked final course
      if (prereqs[i][1] === disliked) {
        // delete disliked course array from prereqs
        prereqs.splice(i, 1);
        // return the size of prereqs -
        console.table(prereqs);
        return prereqs.length;
      }
    }
  } else {
    

    console.table(prereqs);
    



    // use concat() to merge all prereqs into one
    const flattenedPrereqs = [].concat(...prereqs);

    const distinctCourses = [...new Set(flattenedPrereqs)];
    // remove all occurences of 'disliked' course and impossible courses
    // from the flattened array
    for(let i = 0; i < distinctCourses.length; i++) {
      if(distinctCourses[i] === disliked) {
        distinctCourses.splice(i, 1);
      }
      for (let j = 0; j < next_classes.length; j++) {
        if (distinctCourses[i] === next_classes[j]) {
          distinctCourses.splice(i, 1);
          i = i - 1;
        }
      }
    }

    console.table(distinctCourses);
    return distinctCourses.length;
  }
  // NOTE: You may use print statements for debugging purposes, but you may
  //       need to remove them for the tests to pass.
}

console.log(countCourses(disliked, prereqs));

This is a sample for output using "linear algebra" as disliked course:

$ node disliked_courses.js 
┌─────────┬─────────────────┐
│ (index) │     Values      │
├─────────┼─────────────────┤
│    0    │ 'Discrete Math' │
└─────────┴─────────────────┘
┌─────────┬──────────────────────────┬──────────────────────────┐
│ (index) │            0             │            1             │
├─────────┼──────────────────────────┼──────────────────────────┤
│    0    │       'Calculus 1'       │       'Calculus 2'       │
│    1    │       'Calculus 2'       │     'Linear Algebra'     │
│    2    │     'Discrete Math'      │ 'Analysis of Algorithms' │
│    3    │       'Algorithms'       │ 'Analysis of Algorithms' │
│    4    │    'Data Structures'     │       'Algorithms'       │
│    5    │       'Algorithms'       │           'AI'           │
│    6    │       'Calculus 1'       │           'AI'           │
│    7    │           'AI'           │    'Computer Vision'     │
│    8    │       'Algorithms'       │        'Networks'        │
│    9    │       'Algorithms'       │   'Operating Systems'    │
│   10    │ 'Analysis of Algorithms' │      'Theory of CS'      │
└─────────┴──────────────────────────┴──────────────────────────┘
┌─────────┬──────────────────────────┐
│ (index) │          Values          │
├─────────┼──────────────────────────┤
│    0    │     'Discrete Math'      │
│    1    │ 'Analysis of Algorithms' │
│    2    │      'Theory of CS'      │
└─────────┴──────────────────────────┘
┌─────────┬───────────────────┬──────────────────────────┐
│ (index) │         0         │            1             │
├─────────┼───────────────────┼──────────────────────────┤
│    0    │   'Calculus 1'    │       'Calculus 2'       │
│    1    │   'Calculus 2'    │     'Linear Algebra'     │
│    2    │   'Algorithms'    │ 'Analysis of Algorithms' │
│    3    │ 'Data Structures' │       'Algorithms'       │
│    4    │   'Algorithms'    │           'AI'           │
│    5    │   'Calculus 1'    │           'AI'           │
│    6    │       'AI'        │    'Computer Vision'     │
│    7    │   'Algorithms'    │        'Networks'        │
│    8    │   'Algorithms'    │   'Operating Systems'    │
└─────────┴───────────────────┴──────────────────────────┘
┌─────────┬─────────────────────┐
│ (index) │       Values        │
├─────────┼─────────────────────┤
│    0    │    'Calculus 1'     │
│    1    │    'Calculus 2'     │
│    2    │    'Algorithms'     │
│    3    │  'Data Structures'  │
│    4    │        'AI'         │
│    5    │  'Computer Vision'  │
│    6    │     'Networks'      │
│    7    │ 'Operating Systems' │
└─────────┴─────────────────────┘
8

Answer 1

I'm assuming this is homework for a course. That's fine, although in the future, please note that in the question.

You have a working solution, so kudos! Nice job. You asked for help analyzing its algorithmic complexity. I'm afraid my brain is not up for that at the moment. But you also asked for improvements, and I can offer a significantly simpler implementation.

However, if you have not yet studied recursion, then you might want to just skip this answer, because it uses recursion, and, while it's not actually that complex a subject, you might want to wait until it's introduced in your studies.

But if you do have some experience with recursion, here's my implementation:

const countCourses = (disliked, prereqs) => {
  const courses = unique (prereqs .flat())
  const ineligible = allDependencies (prereqs) (disliked)
  const eligible = courses .filter (c => ! ineligible .includes (c))
  return eligible .length
}

const unique = (xs) => [... new Set (xs)]

const allDependencies = (prereqs) => (disliked) => unique ([
  disliked, 
  ...prereqs .filter (([p]) => p == disliked) 
             .map (([_, c]) => c) 
             .flatMap (allDependencies (prereqs))
])


const prereqs = [['Calculus 1', 'Calculus 2'], ['Calculus 2', 'Linear Algebra'], ['Linear Algebra', 'Discrete Math'], ['Discrete Math', 'Analysis of Algorithms'], ['Algorithms', 'Analysis of Algorithms'], ['Data Structures', 'Algorithms'], ['Algorithms', 'AI'], ['Calculus 1', 'AI'], ['AI', 'Computer Vision'], ['Algorithms', 'Networks'], ['Algorithms', 'Operating Systems'], ['Analysis of Algorithms', 'Theory of CS']]
const disliked = 'Linear Algebra'

console .log (countCourses (disliked, prereqs))

Our main function is relatively simple. We extract the list of all courses from the list of prerequisites. You do that in your code. I think this one-liner is simpler, but it's a similar technique. It uses the helper unique, which simply moves an array through a Set back to an array in order to remove duplicates. This is simple enough that I might often inline it, but I use it again below, so it's worth pulling out.

Then I call a helper function to collect all the blocked courses. We'll discuss that helper function next. After that we filter the list of all course to those that are not in the blocked list. Doing this with a filter call is significantly simpler than your version, and probably algorithmically much the same. If nothing else it avoids a splice call; I would suggest that it's an extremely rare situation where splice is a good idea.

Finally, we return the length of that array.

But now we need to discuss the helper allDependencies. Again, it looks like this:

const allDependencies = (prereqs) => (disliked) => unique ([
  disliked, 
  ...prereqs .filter (([p]) => p == disliked) 
             .map (([_, c]) => c) 
             .flatMap (allDependencies (prereqs))
])

The first thing we see is the unique wrapper. After we do the rest of our work, we will use this to remove duplicates. (This is the reason I extracted the helper function rather than inlining it in the main function; we use it again here.) The reason is simple enough. Although our main function would work fine if we didn't bother removing duplicates, this looks like a genuinely useful function on its own, so it should be good enough to stand on its own. And that means that if Courses B and C depend upon Course A, and Course D depends on both B and C, we should not include Course D twice in our results. This unique call ensures that.

The main body of that function collects into an array the given disliked course and the result of doing three steps:

• filtering the prerequisite array to find all those items whose first element is the disliked one,
• taking the second element of each of those prerequisites to get the courses directly dependent on the disliked,
• and collecting the results of calling allDependencies for each one of these now disliked-by-association courses.

This last is the recursive step, and it is the one most likely to be challenging. We call .flatMap (allDependencies (prereqs)) .flatMap is an Array method that calls the supplied function on each of its elements and combines the resulting arrays into a single one. We pass it the function allDependencies (prereqs) Note that this is a function, as allDependencies is a function that takes prereqs and returns a function that takes disliked and returns the values. That function-that-returns-a-function technique is extremely useful. But it's not essential We could have written it like this:

const allDependencies = (disliked, prereqs) => unique ([
  disliked, 
  ...prereqs .filter (([p]) => p == disliked) 
             .map (([_, c]) => c) 
             .flatMap (c => allDependencies (c, prereqs))
])

and called it like this:

  const ineligible = allDependencies (disliked, prereqs)

but I find this curried approach to be cleaner.

This may look different from other recursions you've seen, because the base case is not as cleanly delineated as it is in many places. But it is there. We stop when the resulting list of dependencies is empty. We continue to recur until that happens.

I find the main function extremely simple to read, and the allDependencies helper is not too bad. They definitely simplify from your approach.

---

I have no idea of how the runtime efficiency of this answer compares to your version. But the code is cleaner and might even teach a little bit about more advanced techniques. I hope that it helps!