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 t-1 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 general idea of the algorithm is to step through the days of our current transaction row and see if we can add a transaction at any point of the previous row to increase the profit. See the whiteboard below to see the progression through the solutions to optimise time and space.

Inspired by the following great articles/videos:
https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/
https://www.youtube.com/watch?v=Pw6lrYANjz4 (algoexpert video)

Posted in programming | Tagged , , | Leave a comment

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 listing Salaries of Employees ordered by Salary Descending and limit to 1 with offset 2. The problem is that departments with less than 3 employees will return an empty result set for that subquery, so we can make it return 0 by wrapping it in IFNULL(). Finally I order by department name and salary descending to make the output look nicer. I think it is also possible to solve this problem with the subquery logic returning a count distinct of salaries.

Here is the solution runnable online:
https://paiza.io/projects/BIfLpKxnZbaEOIjIk9f9EQ?language=mysql
And here is the code gist:

Posted in programming | Tagged , , | Leave a comment

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 each cell we calculate its DP value by looking at its right and bottom neighbours to determine the minimum exit value we need to satisfy. So the calculated minimum entry value will be min neighbour – dungeon cell value. That calculated min entry value will be our dp cell. After calculating all dp cells our final result will be at cell 0,0 (top left).

Posted in programming | Tagged , , | Leave a comment

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 we store minimum and maximum values. We go through each number setting the max/min of the appropriate bucket for it. Then we go through all buckets figuring out the biggest gap between the buckets. Beware of empty buckets, which we skip. It is also possible to solve with a radix sort.

Posted in programming | Tagged , , | Leave a comment

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 complication is duplicate values. If we have a situation where l == m == r then we need to step forward l and step back r until l,m,r are not the same.

Posted in programming | Tagged , , | Leave a comment

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 slopes. A more accurate way is to remember x and y values and compare them as a whole. However we need to make sure x and y are simplified to their lowest common denominators, so we need gcd.

Posted in programming | Tagged , , | Leave a comment

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 that we need extra information in the stack entries. I used an extra bool flag to indicate whether we’ve handled (pushed) the nodes children. As we go around our loop we check whether the top stack entry has had its children handled and if not then we add the children (right first then left) to the stack and mark it that the children are handled. Otherwise if the top stack node has had its children handled already then we deal with this node, i.e. we add its value to the result vector and pop it from the stack. We have to use this handled children flag as we need to deal with the left children first and then leave the right children for later.

Posted in programming | Tagged , , | Leave a comment

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 if they are valid as there are too many result permutations. So the memoization in the recursive solution is the thing to note. It doesn’t completely remove duplication of branches but it does remove duplication if there are no solutions in a branch. That is the key for solving the tricky test case because it has a b in the middle of all the a’s in s, which makes it impossible to match:

s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
wordDict=["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
Posted in programming | Tagged , , | Leave a comment

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 more increases in a complete pass.

The O(n) solution relies on calculating from left to right to get increasing sequences, where we set candy[i] to 1 + previous one if rating[i] is bigger than previous rating. We do the same for right to left to get decreasing sequences. We then take the max of those two left and right results. There is also a O(n) time and O(1) space solution but that is more complicated.

Here is the source code for the brute force O(n^2) solution:
https://gist.github.com/adamkorg/6308ae6d8c7dfeb42d45c020022b9af3
And here is the code for the O(n) 2 vector solution:
https://gist.github.com/adamkorg/3bb831b738dd1b1658149d1580357b0d
And here is the code for the O(n) 1 vector solution:

Posted in programming | Tagged , , | Leave a comment

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 and recurse left and right of the cut. Keep track of each return and set minCuts return if smaller. We can apply DP to that recursive solution to get O(n^3) but that is still too slow for the leetcode test cases. An iterative DP O(n^2) solution does pass the leetcode test cases.

The simple slow recursive solution:
https://gist.github.com/adamkorg/d743bd068ed0bdcff060d25e5f905ec0
Recursive with DP:
https://gist.github.com/adamkorg/a2a6079ae2c3f300ee99e98594b6252a
And below is the iterative DP solution:

Posted in programming | Tagged , , | Leave a comment