Stokastik

Machine Learning, AI and Programming

Tag: Leetcode

LeetCode : Largest Rectangle in Histogram

Problem Statement Solution : At first glance, one can say that a brute force approach would take time complexity. That is correct. Let me begin first with the brute force approach explanation. In order to find the largest rectangle possible, scan each of the unit one rectangle (i.e. the heights given in the input array) and then for each such rectangle i compute the maximum possible width it can be […]

Continue Reading →

LeetCode : Smallest Rotation with Highest Score

Problem Statement Solution : As we can see that, we can easily come up with a solution. Rotate the array each time and compute the score. There are N possible rotations for an array of size N, and for each rotated position, computing the score for the array takes O(N) time complexity. Since the approach is very easy, we will not code this approach but will explore whether we can […]

Continue Reading →

LeetCode : Dungeon Game

Problem Statement Solution : This problem is probably towards high medium difficulty level but below the hard level of problems. At one glance, one can conclude that we can solve this problem using the dynamic programming technique and it is correct. The only difficulty is in identifying what value to memoize at each step during the King's journey towards the Princess. So this is how it works. The initial health […]

Continue Reading →

LeetCode : K Inverse Pairs Array

Problem Statement Solution : One of the strong heuristics that I generally use for solving counting problems in programming is that it is most likely a dynamic programming problem and most of the cases it is true, since most such counting problems can be defined recursively. In this problem, of counting the number of k-inverse pairs in an array of size 'n' (from 1 to n) can be defined recursively. […]

Continue Reading →

LeetCode : Cherry Pickup

Problem Statement Solution : This problem is probably one of the most difficult path traversal problem, I have seen on LeetCode and I will let you know the reason why. The most faulty assumption to begin with is that, this can be solved using a greedy approach, i.e. find the maximum possible cherries during the forward traversal (0,0) to (N-1, N-1) and then find the maximum possible cherries during the […]

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 →

LeetCode : Swim in Rising Water

Problem Statement Solution : One possible solution is to see whether for each water level, he can swim from (0, 0) to (N-1, N-1) without waiting anywhere in between. To check whether he can swim fromĀ (0, 0) to (N-1, N-1) i.e. there exists a path, we can use DFS or BFS to traverse the matrix. He can swim from point A to B if the height of B is less […]

Continue Reading →