Leetcode OJ: Recover Binary Search Tree

Recover Binary Search Tree

 

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure. 

An O(n) space algorithm is straight-forward. One can write the in-order traversal of the BST to a linear array, then find the two swapped elements and swap them back.

A better solution is to not explicitly write the in-order traversal to an array. In fact, we can just do an in-order traversal on the BST itself and find the swapped elements in the process. Notice that if we exchange two adjacent (in terms of in-order) nodes, then the logic to find swapped elements is a little different, but this is handled subtly in the code.


However, since the previous solution uses recursion, then the worst case space complexity is the depth of the tree, which could be as bad as O(n).

A tree O(1) space solution requires the used of Threaded Binary Tree, which I learned from other's solution. A threaded binary tree allows one to truly traverse a binary tree with constant space. In our case, we want a forward traversal, so the right child of any node who doesn't have a right child points to its in-order successor. Since we want to preserve the structure, we make that pointing on the fly and recover it after that pointing after use. A threaded binary tree solution is as follows. Notice that we need to find the in-order predecessor of each node twice. The total complexity of finding in-order predecessor of all nodes is O(n), since it's easy to see that every edge is traversed only once. So it is not too bad.

LeetCode OJ: Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

A typical DP. However, a naive O(N^3) time, O(N^2) space solution can not path large test cases. So 3 optimizations are used.

(1) Suppose s and p are of length n and m respectively, then we want to compute a m by n boolean matrix F, where F(i, j) is true if the first i letters of the pattern matches the first j letters of the string. However, we do not need to store then entire matrix, as we can compute the matrix row by row, where the computation of any row only relies on the previous row. Only 2 rows are needed at any time and the space complexity is reduced to O(2*N)

(2) It's easy to see that the '*' is the cause of the O(N^3) complexity, so a simple optimization is to collapse all adjacent '*' into one, which will not change the language represented by the pattern.

(3) When N is very large, like tens of thousand, then even O(N^2) is too slow. We say a non '*' character in the pattern as a hard character, as it must match at least one character from the input string. If we have k hard characters among first i characters of the pattern, then we know F(i, j) must be false if j < k. In this way, we can find a lower and upper bound of j between which F(i, j) can be true for any fixed i. This optimization is especially useful when the pattern is very long, but most of characters in the pattern are hard.

An solution using the above three optimizations is as follows.

LeetCode OJ: Word Ladder I/II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

The above description is for Word Ladder II. Word Ladder one only require you to return the length of shortest path, which will be 5 in the above example.

The output part is basic DFS, and the key part is to find a parent map for the single source shortest path problem. Normally, when we have a graph G(V, E) and a single source s, Dijkstra's algorithm will build a parent map P: V -> V, which can be used to find the shortest path to any destination t from s. P(t) is simply the vetex v, such that path s->...->v->t is the shortest path from s to u. In Word Ladder II, since we are interested in not only one shortest path, but all shortest path, this parent map must be mapping from V to a subset of V, i.e. P: V -> V^2, as there might be more than one parent of a given vertex and we want to get all of them.

A simple modification of Dijkstra will work. Usually, when the temporary minimum distance of a vertex u is updated, we let the vertex v that updates it to be its parent. Now, we add the v to the parent set instead. When the minimum distance is decreased, we clear the original parent set and then add v; when the new distance is the same as the minimum distance, we add the v.

An accepted implementation is as follows:

Notice that we used the adjacency list and priority queue for optimal performance. Otherwise it can not pass the large test cases.

Suppose we have n words in the dictionary, each word is at most m characters long, then a naive way to create the adjacency list by comparing each pair of words suffers O(m*n^2) complexity, which is unacceptable for large n like 20000. In my implementation, we instead find neighbors of a word w by trying to change each of its letters to another one, and the complexity is reduces to (m*n*26).

For the PriorityQueue implementation in Java, decreaseKey operation (decrease the priority of a node given its reference, the priority queue shall rearrange to keep heap property), which is used in Dijkstra's algorithm is not supported. Rather than implement my own priority queue with this operation, I simply insert a node with the decreased key instead. In this way, there will be more than one node for the same vertex in the priority queue, one with the newest/smallest key, whereas the rest are with previous large keys. Since we can keep track of the smallest temporary distance of all the vertices, we can simply ignore a node with key larger than that when doing a removeMin operation. A simple analysis show that this will potential result in larger heap, so the complexity is increased from O(E + VlogV) to O(E + VlogE), which is essentially the same since logE is at most 2logV.

BFS can also be used for this problem since edge weights are uniformly one. Similar, one need to maintain a parent map that is one to many instead of one to one. An BFS implementation is as follows. The running time on LeetCode is not better that the Dijkstra one. Both of them takes more than 1000 ms. Maybe Java is too slow?

LeetCode OJ: Max Points on a Line

This LeetCode problem has the second lowest AC rate. It deserves some attention as it asks for the use of hash table and choice of hash function that requires some thought.

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
note: the points have integer coordinates.

A naive O(n^3) algorithm will consider all pairs of points (p_i, p_j), then for all k != i or j, check whether p_k is on the line defined by p_i and p_j. Identical points needs to be taken care of. An implementation of O(n^3) algorithm is as follows:

A better O(n^2) solution is possible by using hash tables. Notice that this problem is known to be 3SUM-hard so a non-parallel, non-randomized algorithm is unlikely to be better than O(n^2).

To implement a O(n^2) algorithm, one need to create a hash table whose key is encoding of line. One way to encode a line in 2D plan is using slope-intercept form: y = mx + b. However, a and b could be float numbers even if x and y are integers and it is well-known that equality test for float number is error-prone. Instead, I choose to use the standard form: ax + by + c = 0. If we have two distinct points (x1, y1) and (x2, y2), then we can set a = y2 - y1, b = x1 - x2, c = y2 * x1 - y1 * x2, and all of a, b and c will be integers. However, this (a, b, c) is not unique as any integral multiple of it represents the same line. To guarantee uniqueness, we require b to be nonnegative. If b is zero, i.e. the line is vertical, then we require a to be positive. Notice that a and b can not both be zero.

We need to find a good hash function in order to use this (a, b, c) representation as key of hash table. The hash function for hashing integer vectors mentioned in my last post is a good candidate. In particular for the problem at hand, I used:

h(a, b, c) = a + b * 31 + c * 31 ^ 2.

The algorithm itself is straightforward. For each point p_i, we consider all points after it {p_i+1, ..., p_n}. We create a hash table whose key is (a, b, c) tuple and whose value is the number of points in {p_i+1, ..., p_n} that connects to p_i by the line represented by the corresponding key. The the largest value in the constructed hash table is the maximum number of points that lie on the same straight line if the smallest index of those points is i. An implementation is as follows:

Interestingly, the running time of O(n^2) and O(n^3) solutions are not very different on LeetCode OJ, which is probably due to large overhead and small testing cases.

Choice of Hash functions for integer k-tuple in Java

In theory classes, we learn about Universal Hashing, Perfect Hashing, Cuckoo Hashing, Tabulation Hashing, so on and so forth. Most of those techniques enjoy great theoretical value, yet face difficulties in practice. For example, Universal Hashing asks as to encode some randomness into the hashcode() method, which is hard to achieve and we would rather just hard code some coefficient a and b. On the other hand, we rarely in practice need to consider adversarial guarantees. For another example, we simply don't want to afford the creation time and large constant factor of a Perfect Hashing.

We often find ourself just want a hashcode() function for a class whose object is uniquely identified by a k-tuple of integers (a1, a2, ..., ak). Since the HashMap in Java already has a CRC style Hash function to map integer to bins, the hashcode() function only need to convert the k-tuple into a single integer. The following one is what Java uses to hash a String, and is what I suggest to use for hashing k-tuple of integers:

h((a1, a2, ..., ak))
= a1 + a2 * p + a3 * p^2 + ... + ak * p^(k-1)

There is an implicit module operation due to potential integer overflow. Also, it seems people often choose a Mersenne prime for p, such as 31.