1 day agoTwo slow and one fast pointer142. Linked List Cycle II This problem is cool as we need using several pointers to solve the problem with memory complexity of O(1). Here I am explaining everything in one figure. C++ class Solution { public: ListNode *detectCycle(ListNode *head) {…Two Pointers1 min read

Jan 8A 3D DP problem1463. Cherry Pickup II — This problem looks hard at the beginning, however, if you read it carefully and figure our all possible things that can define the unique states, you will find the solution. What we need are: A’s location, B’ location, A + B ‘s current value A and B’s moving directions Special case where a and…Dynamic Programming2 min read

Jan 8An interesting topological sort algorithm2115. Find All Possible Recipes from Given Supplies Naively find until can not find any new recipe If we find a new recipe, then add it to the supplies. Repeat this process until no new recipe can be found. Time complexity: The worst case each time we find one recipe. The total complexity will be O(sizeof(recipes)*sizeof(recipes)*sizeof( ingredient)) = O(100³)…Topological Sort2 min read

Jan 5Backtrack and bit manipulation131. Palindrome Partitioning For this problem, we can put a separate after the position i or not put a separate. In total, we will have 2^(n-1) cases to put the separators. We can solve it by using backtrack bit manipulation The time complexity is: O(n * 2^n ) where O(n)…Backtracking2 min read

Dec 19, 2021LIS: minimum operations to make the array K-increasing2111. Minimum Operations to Make the Array K-Increasing — This is the 4th problem of this week’s LC weekly contest. Explanation We can change the problem to find the LIS for each subsequence with index of 0, k, 2k, … 1, k+1, k + 1 + k,… A well know problem of longest increasing or non decreasing subsqeuence problem. By…Lis2 min read

Dec 16, 2021Diameter of a tree and topological sort310. Minimum Height Trees Explanation For the problem listed here, it is quite interesting as we can: use the diameter of a tree template to solve it use the topological sort to solve this one. Using diameter of a tree Here is my observations: The result at most have two nodes. 1) when the longest path’s…Diameter Of Tree3 min read

Dec 2, 2021How to upgrade cmake in ubuntu3 steps apt remove cmake pip install cmake --upgrade sudo ln /usr/local/bin/cmake /usr/bin/cmake You can use the following command to check the cmake version cmake --versionCmake1 min readHow to upgrade cmake in ubuntu3 stepsapt remove cmakepip install cmake --upgradesudo ln /usr/local/bin/cmake /usr/bin/cmakeYou can use the following command to check the cmake versioncmake --version

Nov 23, 2021Union Find and Prime Factorization952. Largest Component Size by Common Factor Union Find is a natural way to combine different sets with connection into one set. So the basic idea is: If two numbers have common factor, union them During the union process, maintain a set size as the final answer is asking for…Union Find3 min read

Nov 21, 2021Python itertools.product2081. Sum of k-Mirror Numbers This week’s (weekly 268)last question can be solved by checking all the possible numbers in a brute force way. In order to construct all the possible candidates, we can use backtracking based on standard approaches. If you are using python, luckily, we can use itertools.porduct…Python2 min read

Nov 19, 2021Use Union Find to solve a hard problem2076. Process Restricted Friend Requests Are you sure you really master the UF data structure/algorithm? If you are, you can use this question to verify your skills of using UF. This is the 4th question of the LC weekly 267 contest. It is pretty fun. Basic ideas basic UF + maintain members…Union Find2 min read