Machine Learning, AI and Programming

Tag: BFS

LeetCode : Bus Routes

Problem Statement Solution : Observe that one can switch from one route to another route, if both the routes have at-least one stop in common. Starting with the source stop S, there could be multiple possible bus routes R that includes this stop. Thus for every possible route R that include the stop S, do a Breadth First Search to all possible routes R' reachable from this route. R' can […]

Continue Reading →

LeetCode : Cutoff Trees for Golf

Problem Statement Solution : My solution in Python for this problem is not accepted as of yet due to "Time Limit Exceeded". There is no trick that reduces the worst case time complexity for this problem. The straightforward approach is to first sort the tree heights smallest to largest (ignoring the tree heights with height < 1) and then for each successive pair (A, B) of sorted tree heights, do […]

Continue Reading →

LeetCode : Reaching Points

Problem Statement Solution : The obvious way is to go with a DFS or BFS like approach. Starting from the point (sx, sy), we can go in two possible directions (sx + sy, sy) and (sx, sx + sy) and then each of these points can go in two possible directions and so on. Note that the paths will form a tree like structure as we are going in either […]

Continue Reading →