Solving this problem in O(n) time and space relies on using a hash set to store all numbers. You then go through each element in the array and see if a[n]-1 is in the set, and if it isn’t then we know this is the start of the sequence and we look up subsequent numbers to see how long the sequence is. It works out to O(n) time and space, assuming unordered_set is O(1) lookup.
I used a similar approach to Word Ladder I (leetcode 126), where I used BFS to go through all adjacent words (1 character different). The main difference is that I need to keep track of the whole path, which I do as an array in the queue rather than just one word. I also needed to delay marking used until the end of level because we can have multiple routes of the same size but have different beginnings. In order to not TLE I had to optimise the word matching for large word sets, where I used an unordered_map as a dictionary of the words and then I search every letter combination that is one character different.
My first attempt was too slow as it went through each word in wordList checking if the current word was one character different:
https://gist.github.com/adamkorg/c6d49a4e11932e1133aad380d528fb00
I optimised this for large wordLists to use a hashmap to search for all permutations of 1 character different strings, which passed the leetcode test cases:
The key here is that a single path through a node (through one child of the node rather than two) is fairly easily handled by using bottom up preorder traversal and checking which is bigger out of the left and right branch. The complication is if the path goes from one child through the parent to the other child. In that scenario the thing to realise is that the path cost is completely known at that stage as it consists of left branch cost + right branch cost. It does not go up at all. So we need to keep track of that dual child cost separately and I used a reference parameter maxCost for that. I included the single path cost in the maxCost calculation also, so maxCost is the final result.
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.
Here is the code without memoization:
https://gist.github.com/adamkorg/5cee9720741ec9cbe9f83ba2391f99b8
And here is the code with memoization:
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. The idea is to recursively try all possibilities until we reach a complete match. At each step we either move forward one position in s1 and s3 of the current characters are the same or we move forward one position in s2 and s3 if those characters are the same.
In solution B below I used iterative DP. I used a 2D DP table with booleans to signify if reaching those positions in s1 and s2 is possible. Build the table by using the next character in s1 by moving down or using the next character in s2 by moving right. So we can figure out a dp result by building on previous results up and left. Our final result at the bottom right of the table is wether it is possible to get to the end of both strings s1 and s2.
Here’s the iterative DP solution:
https://gist.github.com/adamkorg/a90aaf22791215c44bfffae9f3f4ca6e
And here’s the recursive with memoization solution:
We can use the Largest Rectangle in Histogram algorithm from leetcode 84, repeatedly over rows of column counts. This results in O(Rows * Cols) time and an extra O(Cols) space.
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.
