Tag Archives: leetcode

Leetcode 85: Maximal Rectangle

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.

Posted in programming | Tagged , , | Leave a comment

Leetcode 84: Largest Rectangle in Histogram

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 … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 76: Minimum Window Substring

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 … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 72: Edit Distance

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 … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 71: Simplify Path

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. … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 70: Climbing Stairs

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. … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 69: Sqrt(x)

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 … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 68: Text Justification

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 … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 67: Add Binary

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.

Posted in programming | Tagged , , | Leave a comment

Leetcode 66: Plus One

Straightforward. Just add one to the rightmost number and then perform a carry to next significant digits if necessary.

Posted in programming | Tagged , , | Leave a comment