Tag Kahn's algorithm

LeetCode 2115. Find All Possible Recipes from Given Supplies

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/description/

Note: Since the problem explicitly demands dependency, and the recipes are the ultimate nodes that have indegrees topological sort is the most intuitive thing that can come to mind if you know the idea of the topological sort well. I used Kahn’s algorithm here to do the topological sort.

  • Time complexity: O(n)
  • Space complexity: O(n)
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, vector<string> > ump;
        unordered_map<string,int> indegree;
        vector<string> ans;
        for(int i=0; i<ingredients.size(); i++)
        {
            for(int j=0; j<ingredients[i].size(); j++)
            {
                 ump[ingredients[i][j]].push_back(recipes[i]);
                 indegree[recipes[i]]++;
            }
        }
        for(int i=0; i<supplies.size(); i++)
        {   
            for(int j=0; j<ump[supplies[i]].size(); j++)
            {
                string adj=ump[supplies[i]][j];
                indegree[adj]--;
                if(indegree[adj]==0)
                {
                    supplies.push_back(adj);
                    ans.push_back(adj);
                }
            }
        }
        return ans;
    }
};