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.
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.
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:
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.
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.
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.