Stokastik

Machine Learning, AI and Programming

Tag: Greedy Algorithm

Leetcode : Course Schedule 3

Problem Statement Solution: An obvious brute force approach is to enumerate all possible scenarios i.e. all possible valid sequence of courses and take the answer as the sequence with the maximum length. For an input size of N and a sequence of length M, the number of possible sequences is exponential in N i.e. NM. Obviously this is a bad choice, but can we think of a better solution. We […]

Continue Reading →

Leetcode : Minimum Cost To Merge Stones

Problem Statement Solution: It might be 'tempting' to think that the problem can be solved using a greedy approach, i.e. merge the K consecutive stones with the minimum cost in each step. But the greedy approach is not optimal, for e.g. if the stones array is [6,4,4,6] and K=2, then the greedy approach would result in a minimum cost of 42 whereas the optimal cost is 40. The greedy approach […]

Continue Reading →

LeetCode: Minimum Refuel Stops

Problem Statement Solution: At first, this looks like a classic graph traversal problem. For example, I might be tempted to use BFS approach to find the minimum number of steps to reach the target. But one important distinction this problem has from a standard BFS is that in a standard BFS problem, the car can either directly reach a station Y from station X or they cannot depending whether there […]

Continue Reading →