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.

Recent Posts
Recent Comments
Archives
Categories
Meta
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.
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.
Here’s the source code for that initial solution:
https://gist.github.com/adamkorg/36adeab8156778d3852c37a57fb250aa
And here’s the source code for the simplified getline()/stringstream solution:
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.
The way I solved this was through a binary search algorithm, where I started out with 0 and x as the lower and upper bounds. Then find the mid point and test by squaring it. If the square is equal to x then we have our answer. If the square is smaller than x then we need to lower our search, so we reduce our search range by looking between 0 and mid. If the square was bigger than x then we search between mid and x. We repeat this until we the range is size 1. There are a few edge cases to consider:
1) Overflow: I overcome this by checking against a limit for mid so that the square cannot exceed the integer limit. I noticed on leetcode that most solutions use a long variable to calculate the square, which on Unix systems (LP64) will work but not on Windows (LLP64).
2) Upper bound check: It might be possible that at our loop end condition, we haven’t checked the upper bound. So I check this out of the loop.
I quite liked this problem even though it seems to have a lot downvotes. It takes a while to solve because there is quite a lot of logic to encode but it is very doable. For me it was important to plan out the complicated case of the variable length spacing of multiple words on nonlast lines. I thought through how to calculate these spaces by defining a bunch of dependant variables.
Similar to the previous problem (Leetcode 66 – Plus One). Loop around both input strings from last char to first char. Add each digit and remember carries if needed.
Straightforward. Just add one to the rightmost number and then perform a carry to next significant digits if necessary.