Leetcode 44: Wildcard Matching

There were some tricky test cases in this problem that meant my original recursive solution was too slow. My second attempt was inspired by this post:
http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html

The solution basically steps through matches and then if it finds a * wildcard pattern character then it stores its positions in the pattern and string. It then attempts to just step past the wildcard and if at some point it fails then it rewinds back to the original position but skips forward one position in the string. So it tests out further matches by using an increasing number of characters used by the wildcard.

Here are my whiteboard notes where I try to explain the logic. Note that I use the cs and cp variables as the indexes of the current positions in the pattern and string. However at the top of the whiteboard I started out using “is” and “ip” instead of cs and cp. I also use sp for the star position in the pattern and ss for the position of the star matching in the string.

I think this has a worst case time complexity of O(n²). I think it might be possible to use the KMP algorithm to achieve O(n) but that is quite a bit more complicated. I think this solution is far more elegant. Here is the c++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 43: Multiply Strings

The general steps to do long multiplication are fairly straightforward but the implementation was a bit fiddly. I think it would be easier to to reverse the strings and work on them in reverse, then the least significant index will be zero. It is a bit fiddly to do the other way, which is how I did it below:

And the c++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 42: Trapping Rain Water

This is a tricky leetcode problem. There are a few observations that need to be made. Water traps between two bars and only fills each of those gaps to a volume that is the gap’s height taken away from the smaller of the two enclosing bars’ height. It is easier to calculate if the two enclosing bars are ascending, in which case we just compare each gap’s height to the first bar’s height. Descending is more tricky as we need to look ahead to find the next tallest bar and that requires an extra array pass, which would result in O(n²). We can use a two pointer (left and right) technique to ensure that we are always solving ascending bounding bars. We just iterate the pointer that has the smallest enclosing bar (max height bar). Here are my whiteboard notes, which might make it clearer:

And here are is my c++ source code for the solution:

Posted in programming | Tagged , , | Leave a comment

Leetcode 41: First Missing Positive

This is tricky and probably not typical of a real world problem, so I don’t know how useful it is know. Given the criteria of running it O(n) time and only using constant extra space, the only way we can solve this is by rearranging the array. As we know that we don’t need to consider negative numbers, we can use negatives as switches for each element position. A negative will mark that we have a number equal to the element’s index. As we sequentially read through the element values, we will mark them off by looking up indexes by using the values, so for value a[i] we will look up a[a[i]]. We then do another pass to find the first non-negative value, which marks the first missing positive. Here are my whiteboard notes:

And my c++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 39: Combination Sum

This is a problem that fits naturally to a recursive solution. I’m not sure how I’d implement without recursion. The recursion automatically does a backtrack to find valid solutions. By starting the search for sub-items from the current item and bigger, we eliminate duplicates as the numbers will be in ascending order. Here are my whiteboard notes:

And the c++ source code for my solution:

Posted in programming | Tagged , , | Leave a comment

Leetcode 37: Sudoku Solver

This was an interesting problem that highlights that sometimes it is better to write an algorithm for a computer to execute in a different way to how we would solve the problem with a human mind. So I first attempted to code this in a way in which I would manually solve a sudoku puzzle by walking through each number and analysing the impact of rows and columns on boxes. This resulted in complicated code and did not work on hard sudoku puzzles.

My second attempt at a solution used backtracking. The result was simpler code and the ability to solve the hardest sudoku puzzles. The algorithm stops at every space sequentially and tries every number until it finds a number that results in a valid board. If it gets to a square where no number will work then it backtracks to the previous square and continues its search through the numbers. Here is a nice visualisation of backtracking from wikipedia:

Here is my c++ source code for the solution:

Posted in programming | Tagged , , | Leave a comment

Leetcode 32: Longest Valid Parentheses

This was probably the easiest leetcode “hard” question that I’ve done so far. My first attempt worked on the two examples in the description but failed on the following test case “()(()”. My first attempt just used counters and did not use a stack. It reset the valid sequence when the current open bracket counter went to zero and we encountered a close bracket. It did not account for an unmatched open bracket in the middle as in the failed test case above. So to address that I keep track of a stack of open brackets with their positions in the string as the stack values. I also keep track of matched bracket positions in a boolean array. Here are my whiteboard notes:

Here is my c++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 31: Next permutation

Here are my whiteboard notes for solving this:

So it turns out this algorithm was first discovered a long time ago. According to Knuth (in The Art Of Computer Programming 7.2.1.2), it goes back to the 18th century. This is a nice writeup of the algorithm:
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

Here is my c++ source code for the solution:

Posted in programming | Tagged , , | Leave a comment

Leetcode 25: Reverse nodes in k-group

My first thoughts for reversing the group was to have start and end pointers, switching those and then moving pointers one step inwards. This is logically how I would tackle reversing array elements but it does not work well with a linked lists (lots of traversing for end pointers and then keeping track of surrounding pointers). I then realised that we could reverse a group of nodes by traversing along the group using three pointers and adjusting those pointers as we go. We can then keep track of the last pointer of the previous group to link groups together. Here are my whiteboard notes:

And here is the c++ source code for the solution:
https://gist.github.com/adamkorg/9f6326b58db32210d9542bd1287133f9

Posted in programming | Tagged , , | Leave a comment

Leetcode 23: Merge k sorted lists

Here are my whiteboard notes for solving this problem:

And here is my c++ source code for the solution:

https://gist.github.com/adamkorg/fb698c0785845576ff0b42a091547691

Initially I started off with what I thought was a simple inefficient way of finding the next smallest node but the implementation was actually a little complicated. The multimap version is more time efficient and possibly has less complicated edge cases. I think an even more efficient way to keep track of the smallest node would be to use a priority queue.

Posted in programming | Tagged , , | Leave a comment