
Recent Posts
Recent Comments
Archives
Categories
Meta
Tag Archives: algorithms
Leetcode 188: Best Time to Buy and Sell Stock IV
To solve this we can use Dynamic Programming to gradually build upon previous solutions for t1 transactions. The simplest to understand solution uses O(n²k) time and O(nk) space. We can optimise the time to O(nk) and space to O(n). The … Continue reading
Leetcode 185: Department Top Three Salaries
Join Employee and Department tables by DepartmentId. In WHERE clause we need to filter to show only salaries higher than a subquery result. In that subquery we will try to return the third highest distinct salary. Do that subquery by … Continue reading
Leetcode 174: Dungeon Game
My first attempt, where I tried top down DP, didn’t work. My second attempt used bottom up DP where I start from the last cell (bottom right) and work my way through to the first cell (top left). So at … Continue reading
Leetcode 164: Maximum Gap
I used bucket sort (pigeonhole principle). So we create nums.size() buckets and we spread them out at a distance that is equal to uniformly distributed set spread (which is the smallest maximum gap we could possibly have). For each bucket … Continue reading
Leetcode 154: Find Minimum in Rotated Sorted Array II
Draw out various use cases. We can see that if left < right then left is the minimum. Do a binary search. If r < m then search right half. Otherwise if m < l search left half. The one … Continue reading
Leetcode 149: Max Points on a Line
For every point we need to compare the slope to every other point and remember the most that are the same. The obvious way to calculate slope is y/x but that could suffer from floating point rounding errors when comparing … Continue reading
Leetcode 145: Binary Tree Postorder Traversal
A recursive solution is very simple, it just recurses into the left node then recurses into the right node and then handles the current node. The iterative solution is more difficult to come up with. The trick with iterative is … Continue reading
Leetcode 140: Word Break II
The easiest way to solve this is recursively with memoization. Note that there is a horrible test case that makes my iterative DP solution fail. That test case is not fair because those sorts of length strings will never work … Continue reading
Leetcode 135: Candy
In the O(n^2) solution we just start with all 1s and then we step through each element and if ranking[i] is bigger than it’s neighbours and candy[i] is not then add 1 to candy[i]. Repeat that until we make no … Continue reading
Leetcode 132: Palindrome Partitioning II
The obvious fairly simple recursive solution is very slow (exponential). The recursive base case start>end is 1 char or isPalindrome(start>end) return 0 cuts. In the recursive function we go through each character in the range trying to place a cut … Continue reading