Machine Learning, AI and Programming

Tag: BFS

Leetcode : Redundant Connections 2

Problem Statement Solution: The brute force approach for this problem would be to do a DFS or BFS starting from each node after removing edge Ei in the input 'edges' array. At each position i from right to left, after removing Ei, do BFS from each node in the graph. If for BFS from any node, we cover all the nodes from 1 to N without any cycle, then return […]

Continue Reading →

Leetcode : Cutoff Trees for Golf

Problem Statement Solution : There is no trick that reduces the worst case run-time complexity for this problem. The brute-force approach is to first sort the tree heights from lowest to highest (ignoring the tree heights with height < 1) and then for each successive pair (A, B) of sorted tree heights, do a BFS from A to B and compute the minimum length path required to travel from A […]

Continue Reading →

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 : 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 →