What 's the complexity of this algorithm ? (bfs, shortest)

Viewed 51

What the complexity of this algorithm is? I want to express the complexity of big-O. I don't know for the life of me.

Problem: req_skill : list of required skills people : ith person people[i] contains a list of skills that the person has. Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill.

Example 1: Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] Output: [0,2]

Solution:


class Solution:

 def smallestSufficientTeam(self, skills: List[str], people: List[List[str]]) -> List[int]:
    
    # Contains a set with each person containing the skill in the skill
    skill_list: List[Set[str]] = [set() for _ in skills]
        
    # Map w/ skill to index (to fill skill_list easier)
    skill_map: Dict[str, int] = {skill: i for i, skill in enumerate(skills)}
    
    # Fills skill_list with index of skill containing person having skill
    for i, person in enumerate(people):
        for skill in person:
            skill_list[skill_map[skill]].add(i)
    
    # Queue for bfs. Passing in skill_list and current chosen people
    queue: List[Tuple[List[Set[str]], List[int]]] = []
    queue.append((skill_list, []))
    
    while queue != []:
        top_skill_set, top_people = queue.pop(0)
        
        # Picks skill w/ smallest number of people involved, and 
        for person in list(min(top_skill_set, key=len)):
            # Eliminates all skills that "person" has
            new_skill_list = [skill for skill in top_skill_set 
                              if person not in skill]
            
            if new_skill_list == []:
                # If no more skills left, this is shortest group yet
                # Note: Because this is a BFS, this will always be shortest
                return top_people + [person]
            else:
                # Add new_skill_list to queue
                queue.append((new_skill_list, top_people + [person]))
                
    return []  # If no solution exists, return empty array

question: https://leetcode.com/problems/smallest-sufficient-team/ code : https://leetcode.com/problems/smallest-sufficient-team/discuss/1402490/Python-Solution-(24ms-beating-100)

thank you very much.

1 Answers

Since you are doing BFS. The actual running time is O(V + E), where V is vertex and E is edge, as each is counted once.

However, depending on E (which could be skills in this case), best-case is O(1) and worst is O(V^2) -- BFS is binary tree so max of two connections.

Take a look at these sources (They go into much more detail):

https://en.wikipedia.org/wiki/Time_complexity https://www.comp.nus.edu.sg/~cs1020/tut/15s2/tut09ans/T9_ans.pdf

For graphing BFS: https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/?ref=lbp

Related