Stokastik

Machine Learning, AI and Programming

Tag: Leetcode

LeetCode : Count of Range Sum

Problem Statement Solution : This one looks like a very simple problem at first glance but I found it to be quite tricky during implementation. The straightforward solution is to pre-compute the prefix sums S(i), i.e. the sum of all integers from 0 to i-th index for all possible i, and then compute all possible range sums S(i, j), which is the sum of all integers from index i to […]

Continue Reading →

LeetCode : Concatenated Words

Problem Statement Solution : This is an interesting problem, not because it is difficult or tricky to find an efficient solution, but there are multiple approaches and each approach is dependent on the problem definition and problem test cases. Identifying words where the space between them has been mistakenly omitted is a classic problem is text processing because this is one way by which search engines such as Google provide […]

Continue Reading →

LeetCode : Unique Letters

Problem Statement Solution : Let's try to build a 'bad' solution first. By 'bad', I mean the approach may not be the most optimal but will return correct results every time. One such approach is to list down all possible substrings and count the unique letters in each of them and then take their sum. This approach is perfectly reasonable approach but why it is not optimal ?

Continue Reading →

LeetCode : Recover Binary Search Tree

Problem Statement Solution : One approach that uses O(n) extra space, is to store for each node N, the pointer to the nodes with minimum and maximum values in the sub-tree rooted at N. Let's denote the minimum node rooted at N by N.min and the maximum  node by N.max. Then for a sub-tree rooted at N, the sub-tree has a "defect", if : N.val < N.left.max.val and/or N.val > N.right.min.val […]

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 : Maximal Rectangle

Problem Statement Solution : A simple brute force approach would require for each pair of points in the matrix, whether the points form the top left and bottom right corner of a rectangle (all 1's) and compute its area. Since there are O(N2) points, thus there are O(N4) pairs of points. Checking whether there is a rectangle between them and computing its area takes O(N2) comparisons. Thus the total run-time is O(N6), […]

Continue Reading →

LeetCode : Maximum Gap

Problem Statement Solution : There were many different approaches that were coming to my mind while beginning to solve the problem, but all of them were non-linear space/time complexities. One thing that I realized was that, if there was some generic O(N) approach that enables us to find difference between any two consecutive numbers in the sorted array, then sorting the numbers itself would be linear. But that is not […]

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