We need to figure out max profit at each day going from left to right and going from right to left. We store those profits in two vectors called let and right. For each element in left we calculate the max profit for that day which is prices[i]-low. So we have to keep track of the lowest prices so far also. In left[i], we set the maximum of the last value or the just calculated max profit for the day. If we use maximums so far in each left and right array then we just need to traverse each element to see which pair of left and right daily maxProfit totals the most.
My first attempt was a recursive solution without memoization, which I suspected would not pass all leetcode test cases and it didn’t. I then modified this to use memoization, which saved doing the same calculations over and over again.
The key observation is that the values should go up in an inorder traversal list and where they go down marks the value out of place. If the two out of place nodes are adjacent then we will have only one number that goes down, otherwise there will be two. See whiteboard to see what the indorder lists look like for some examples.
I used recursion with DP memoization. A simple recursive solution will be O(2n) because there can potentially be a lot of repeating subtrees in the call graph. Memoization cuts out these duplicated paths. It is also possible to do an iterative DP implementation. I simplified the memoization code on gist.
An O(n²) solution is simple but fails time limit on a leetcode test case. The O(n²) solution goes through each element and for each one it finds the next smallest to the left and next smallest to the right. That box will determine the maximum area for that bar.
An O(n) solution involving a stack exists and although the solution is very concise, it is somewhat unintuitive and difficult to follow. It follows similar principle to the O(n²) solution, but we push elements to a stack if they are bigger than previous to deal with them later. As we move through the bars, we are looking for the end of an area box, which is marked when a bar (i) is smaller than that previous bar on the top of the stack. We stop to deal with that top stack bar, so pop it and call it’s index tp. We then go back to the stack (s) to find out the starting bound of the area box, which is marked by the next item in the stack, which is smaller than tp. We calculate the area = heights[tp] * (i – s.top() – 1); unless there is no item in the stack in which case area = heights * i; i.e. span all the way to the beginning.
My solution involves two pointers l and r to mark the begin and end of a sliding window. We will expand by incrementing r and shrink by incrementing l. So while we don’t have a complete window (complete in that it contains all the letters of t) we will expand and then while do have a complete window, we shrink. At every step we check if we have a complete window and if its positions are smaller than the previous one. If it is smaller then remember those positions in min_l and min_r. I implemented with two unordered_maps (one for the sliding window character frequencies and one for string t character frequencies).
I have seen it implemented with a single array where you initialise it to frequencies of chars in t and then you decrement those frequencies as you come across them in the window. When you get to zero then that means you’ve got the required amount. Less than 0 and you have more than the required amount and in that case you don’t add to count. That’s a clever solution but I think my one is more intuitive and easier to follow.
This problem is also known as the Levenshtein distance. It is possible to solve recursively but that is very inefficient. Here is how to do it with dynamic programming. My initial logic didn’t work with recurring characters. I’ve highlighted the fix in red.
My original solution (whiteboard notes below) involved manually parsing the directory names by stepping over characters one by one looking for the slash character. This was somewhat fiddly and error prone and required some fixes after trying the test cases. I reimplemented using std::getline() and stringstream to do the tokenising, which proved simpler and less error prone. See gist source code for that implementation below.
I went down some time consuming dead ends on this problem. I focused on combinations and binomial coefficients. But these suffered from number variable overflow. What I initially missed was that the results of each n follows a fibonacci sequence. It is easy once you realise that.