Leetcode 50: Pow(x, n)

A few fiddly cases of exponentiation to deal with in this problem. A simple O(n) solution is fairly straightforward but that will not pass some of the leetcode test cases. An implementation that uses binary exponentiation will work in O(log n) time and will pass the leetcode tests. One other fiddly edge case was the test case that used INT_MIN as the exponent, which does not allow us to *= -1 for negative exponents, so I had to use long int to expand the range of the exponent. My original binary exponentiation implementation was messy, so the elegant solution below took inspiration from https://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/

Here are my whiteboard notes:

And here is the c++ source code:

Posted in programming | Tagged , , | Leave a comment

SudokuSolverX Android app

I’ve created a Sudoku puzzle solving app. See details here:

Posted in programming | Tagged | Leave a comment

Leetcode 49: Group Anagrams

The most efficient way I could think of to solve this problem was to use an unordered_multimap to store sorted strings as keys and the original strings as values. This will then automatically provide the groupings we need. Here are my whiteboard notes:

And the C++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 48: Rotate Image

The idea with my solution is that you work your way through layers of the box, starting with the outside layer and then moving inwards. For each layer we step through four points at a time, starting at the corners and then working our way around. In the solution below I store those four points in an array and then I call std::rotate() to shift the numbers. I felt this was logically slightly simpler. An optimisation on this would be to use a single temporary variable to store one of the points and copy the other points to each other.

Here are my whiteboard notes:

And here is the c++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 46: Permutations

The obvious way to solve this is to repeatedly call next_permutation() from the standard library. Another way to solve it is to implement what next_permutation() does and I have done that in a previous solution:

I thought I would have a go at solving this by using the nature of recursive calls to go through combinations. The following is a logically simple but not very efficient way of doing it:

And here is the source code:

A more efficient solution is https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ although this does not generate outputs in lexicographical order.

Posted in programming | Tagged , , | Leave a comment

Origins of the C++ name

In Stroustrup’s “A Tour of C++”, it says that C++ takes its name from:

  • The increment operator (++) combined with C programming language name.
  • George Orwell’s novel “1984”.

The first was obvious and expected but the second was surprising, so I did some digging around to find more details.

In the novel “1984”, “Newspeak” was the language of English socialism. Newspeak had three vocabularies. The A vocabulary was for everyday use, the B vocabulary was for political usage and:

“The C vocabulary was supplementary to the others and consisted entirely of scientific and technical terms” – 1984 – George Orwell, p.322

The 1984 novel also describes the meaning of “doubleplus”:

“any word … could be strengthened by the affix plus-, or, for still greater emphasis, doubleplus-.” – 1984 – George Orwell, p.315

Posted in programming | Tagged , | Leave a comment

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:

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