Java PriorityQueue


Java PriorityQueue does not store the whole sequence in-order. So if we try to print it using System.out.println(Q), the output will usually not be in-order. But every time we do a poll() on a priority queue, it will give the smallest number in the current sequence.

Matrix transformation (2)


A second type of matrix transformation problem involves swapping matrix elements in different ways. One example is matrix transpose, which merely involves swapping element A[i][j] with element A[j][i]. A much more interesting example involves matrix rotation, e.g., the “rotate image” problem, which asks us to rotate a matrix by 90 degrees (clockwise or counterclockwise). This rotation problem can be solved through layer-level traversal. But different from the “layer rotation” problem discussed in “matrix transformation (1)“, the relative positions of elements at different layers are fixed in the “rotate image” problem. The following solution is from CTCI v6 page 203. The trick is to introduce 3 additional variables: “first” (start of a row or column), “last” (end of a row or column), and “offset” (index relative to the start).

Matrix transformation (1)


This type of problems are quite different from those discussed in “changing matrix elements” in the sense that the traversal can no longer be implemented using a simple nested loop that goes through row index and column index in order. One example is the “matrix layer rotation” problem, in which each layer of the matrix is rotated counterclockwise by a certain amount, which is different for different layers. In my solution in the following, I first traverse the matrix layer by layer from outside towards center and store the elements in each layer into a separate list. After this re-arrangement of the matrix elements, the elements in a rotated layer can be accessed through indexing as discussed in “querying the rotated array“. I then reconstruct the rotated matrix using the layers with the rotated index. During all those operations, it is important to fix a reference point and I used the upper-left corner, row = 0 and column = 0, as the reference.

A closely related problem is the “spiral matrix” problem, in which we need to traverse the matrix in spiral order. For this problem, it is important to check for corner cases (matrix that is very elongated along horizontal or vertical direction). My solution is the following.

There is also a problem that asks us to reconstruct a matrix from its spiral order traversal (the “spiral matrix II” problem). My solution is the following.

Re-arranging characters


Some of the problems ask us to rearrange a sequence of characters into different forms, e.g., a matrix, and then traverse the rearranged characters in different ways. One example is the “encryption” problem. The logic of the code can often be simplified significantly if we use a special character, e.g., “$”, to fill all the elements after the end of the original character array. My solution is in the following.

Java primitive explicit casts


When multiplying two very big integers together, say “c = a * b”, the result can overflow. If we just make “c” a long integer, the result of the right-hand-side will be implicitly cast from integer to long during the assignment. But that does not prevent the overflow! If “a * b” (the RHS) overflows, the number implicitly cast to long and assigned to “c” is the overflown integer (a negative integer), not the correct answer. So to prevent the RHS from overflow, we need to explicit cast at least one of the numbers on the RHS to long, i.e., “long c = (long)a * b”, in which “b” will be implicitly cast into a long integer and the result of the RHS will be a long before assigned to “c”. One example is the “modified Kaprekar numbers” problem and my code is following.

Convert numbers/words to words/numbers


Some of the problems ask us to convert numbers to English words or phrases, for example, the “time in words” problem, which asks us to convert a time specified using numbers to words. For this type of problems, a HashMap that binds the numbers to their corresponding words can be quite handy. My solution is int the following.

Another related problem is to convert numbers to other types of text representations, such as the “integer to Roman” and the opposite conversion “Roman to integer“. The opposite conversion (from Roman to integer) is simpler. Again, a HashMap is used to map Roman characters to their corresponding integers (the mapping can be found on wiki) in my following solution. The only issue is that some of the Roman numerals are two-character long and both characters also exist in the HashMap as independent keys, so I check for the existence of a 2-character key before checking for the existence of a 1-character key.

Mapping integers to Roman numerals is more complicated. In addition to the HashMap that binds single-character Roman numerals to corresponding integers, we also need a separate simplification map that binds 2-character Roman numerals to corresponding sequences of 1-character Roman numerals. After we map the integer to a sequence of single-character Roman numerals, we apply a simplification process that maps subarrays of single-character Roman numerals to corresponding 2-character Roman numerals. In order to iteration through all the keys in the HashMap in a specific order (decreasing order in my following code), I used a separate array to store the keys in descending order. The following is my code.

Java BigInteger


Java provides a data structure for storing very large integers that cannot fit into the 64-bit long type. It is called “BigInteger”. One example is the factorial calculation (e.g., the “extra long factorials” problem), which can overflow 64-bit long very quickly. My solution using BigInteger is the following.

Java BitSet


Java provide a very convenient data structure for storing bits (true/false) in an array, which is called BitSet. One example that can make use of this data structure is the “ACM ICPC team” problem, in which we need to find a team (two bit arrays) whose combined “1s” cover the most number of bits. My solution is the following.

Combinations (two choices)


In this type of problems, we repeat the same experiment for “n” times and each time the outcome is either “a” or “b” and we are asked to find all possible combinations of the “n” outcomes. One example is the “Manasa and stones” problem. If the number of outcomes with value “a” is “i”, we know for sure that the number of outcomes with value “b” is “n – i”. So we can just loop through all possible values for “i”, which is from 0 (no “a”) to n (all “a”), and store the result of each iteration into a list. My solution is in the following.

Searching a matrix for patterns (2)


In the post “searching a matrix for patterns (1)“, I discussed an example of searching for a specific shape (a plus) in a matrix. In this post, we look at another example, the “grid search” problem, in which we have to search for the occurrence of a rectangular block of numbers.

The basic idea is straight-forward. I first search for the occurrence of the upper-left corner element of the smaller matrix inside the larger matrix. If I find a match, I loop through every element inside the smaller matrix and compare with the corresponding element in the larger matrix. If one of the element does not match, I break out the inner match loops and check the next location where the element in the larger matrix matches the upper-left corner of the smaller matrix. As soon as I find a complete match, I break out the outer match loop. For this type of problems, the ranges of the loops are particularly important and it is very easy to make a mistake. Pay special attention to line 21-22 in my solution in the following.