FIND ALL RECIPES FROM GIVEN SUPPLIES | LEETCODE 2115 | PYTHON TOPOLOGICAL SORT SOLUTION

[@aishwariyaaish8305]

crazily addicted to all your videos, other short videos outside the channel need to be played multiple times to understand fully but every videos in your playlist just require O(1) time to be played to understand and code. Thank you is really underestimated word for this video Thanks Cracking Faang channel :)

[@crackfaang]

Thanks for the kind words and glad you are enjoying the content!

[@iamnoob7593]

Superb thanks a lot man. I coded this in java

[@victoronofiok520]

thanks for this. You don't need the extra set to lookup recipes though since you already have it in your indegree dictionary and its also o(1) to lookup. what do you think?

[@vickydas6480]

Yes 👍

[@samuel2221]

Thank you for the solution. Could you please make a video for these two problems? 1. Maximum Number of Visible Points (1610) and, 2. Range Module (715)

[@crackfaang]

I just made the video for Range Module and I can say with certainty that this is one of the biggest bullshit problems I've ever done. This is so ridiculously hard it's insane

[@YT.Nikolay]

High caloric video :D the hardest part for me is to figure out how to build the correct graph >_

[@subee128]

Thank you very much

[@AhmedGhazey]

class Solution { public List findAllRecipes(String[] recipes, List ingredients, String[] supplies) { Map graph = new HashMap(); Map inDegree = new HashMap(); Set suppSet = new HashSet(); for (int i = 0; i < supplies.length; i++){ suppSet.add(supplies[i]); } for (int i = 0; i < recipes.length; i++){ graph.put(recipes[i], new ArrayList()); inDegree.put(recipes[i],0); } for (int i = 0; i < recipes.length; i++){ List ingredient = ingredients.get(i); for(String ing : ingredient ){ if (!suppSet.contains(ing) && graph.containsKey(ing)){ String parent = ing; String child = recipes[i]; graph.get(parent).add(child); inDegree.put(child, inDegree.get(child)+1); }else if (!suppSet.contains(ing)){ inDegree.put(recipes[i], inDegree.get(recipes[i])+1); } } } Queue sources = new LinkedList(); for (Map.Entry entry : inDegree.entrySet()){ if (entry.getValue() == 0){ sources.add(entry.getKey()); } } List result = new ArrayList(); while (!sources.isEmpty()){ String vertex = sources.poll(); result.add(vertex); List children = graph.get(vertex); for(String child : children){ inDegree.put(child, inDegree.get(child)-1); if ( inDegree.get(child) == 0) sources.add(child); } } return result; } }

[@iamnoob7593]

graph map is not filled

[@MinhNguyen-lz1pg]

Didn't know you need a college degree to cook thessdays

[@johnj171]

nice intimidation liked and subscribed

[@bEaStOFtube]

my solution beats 90% (python): class Solution: def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]: res = [] supplies_set = set(supplies) rec_set = set(recipes) seen = {} def dfs(i): if i in seen: return seen[i] seen[i] = False ing = ingredients[i] can_make = 0 for item in ing: if item in supplies_set: can_make += 1 elif item in seen and seen.get(item): can_make += 1 elif item in rec_set and item not in supplies_set and dfs(recipes.index(item)): can_make += 1 if can_make == len(ing): supplies_set.add(recipes[i]) seen[i] = True return True return False for i, r in enumerate(recipes): if dfs(i): res.append(r) return res