javascript - More Efficient Solution For Looping through Array of Objects and Evaluating Dependencies in Each Object

Question

I recently did a code challenge where I needed to write a function that evaluates an array of objects, each object having a dependencies property that contains the id's of other objects in the array. See below.

var task = [
    { "id": 1, "depends": [2, 3] },
    { "id": 2, "depends": [] },
    { "id": 3, "depends": [2, 4] },
    { "id": 4, "depends": [] }
];

The function should loop through the array and "process" each task if their dependencies have been met and then log it. So in the example above, task #1 gets skipped because it depends on tasks #2 and #3. So next comes task #2. It has no dependencies so we can "process" it. Then we move on to three but it is skipped because it depends on task 4 (not yet processed). Then we get to four, process it, then go back and evaluate the remaining tasks. The expected output should look like the below.

Task #2 is complete.
Task #4 is complete.
Task #3 is complete.
Task #1 is complete.

I was able to find a solution but I feel like there can be a more efficient one in terms of time complexity. I found a question that is similar to what I'm looking for but it's a bit different from my case so wasn't as much help as I'd hoped.

My solution is in the snippet. It's a recursive function that loops through the tasks and if their dependencies have been met, put their id in a map. Then use this map to filter an object's dependencies based on whether or not that dependency is in the map.

var task = [
    { "id": 1, "depends": [2, 3] },
    { "id": 2, "depends": [] },
    { "id": 3, "depends": [2, 4] },
    { "id": 4, "depends": [] }
];

var map = {}

const processTasks = (arr) => {
    
    arr.forEach((t, i)=>{
        if (!t.depends.length){
          console.log(`task ${t.id} complete.`)
          map[t.id] = true
          arr.splice(i, 1)
        } else {
          t.depends = t.depends.filter(x=>{
            return !map[x]
          })
        }
    })
  
    if (arr.length > 0){
      processTasks(arr)
    }
}

processTasks(task.sort((a, b)=>{
    return a.depends.length < b.depends.length ? -1 : 1
}))

question from:https://stackoverflow.com/questions/65872673/more-efficient-solution-for-looping-through-array-of-objects-and-evaluating-depe

Answer 1

Your algorithm has O(N^2 + M) - quadratic complexity (N - number of tasks, M - total length of depends arrays).

You need to find an order of tasks so that if task A precedes task B, then A doesn't depend on B. This process is called topological sorting. After performing that sorting, you can execute tasks in this order in one traversal - O(N). The sorting itself has O(N + M) time complexity, so the whole process will be O(N + M) - much faster.