I'm learning algorithm at LeetCode and HackerRank. This repo contains some techniques and the list of solutions. Solutions are written as markdown files following the naming convention:
leetcode/${id}.${name}.md
- Do you understand the question? Can you rephrase it?
- What is your strategy for the resolution?
- The estimation of time complexity and space complexity?
- Illustrate the solution steps using a simple example?
- Corner cases, are they being considered?
- Any ideas of further optimization? Saying it rather than writing it, because of time constraint, readability, or other reasons.
Boyer–Moore majority vote algorithm. Finding a majority element that occurs ≥ N/2 times. Done in O(N) runtime and O(1) space. See https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm.
Hash code of the array. Returns a hash code based on the contents of the
specified array (overloaded methods: boolean[], byte[], char[],
double[], float[], int[], long[], Object[], short[]):
java.util.Arrays.hashCode(int[] a);2 Pointers (Fast & Slow). One slow pointer and one fast pointer. They both move forwards at same speed unless in some cases, slow pointer needs to stop. This strategy can be used to manipulate the array in place. Example: LeetCode 27 Remove Element.
2 Pointers (Left & Right). Left pointer moves right, right pointer moves
left.
Find Max (Min). Do not use sorting to find max or min values from an array. This can be done using variables and in one iteration. Time complexity: O(N).
Sorting. Sometimes sorting is useful before addressing the real problem. It enables the relationship between neighbour elements. The time complexity is O(N log N).
Permutation. The next permutation in lexicographic order can be generated using the method created by Narayana Pandita, see Wikipedia: Permutation - Generation in lexicographic order
Related problems:
Prefix Sum. In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence. See https://en.wikipedia.org/wiki/Prefix_sum.
Related problems:
Kth Element. Find the Kth largest or smallest element in a collection or array. This can be done using a priority queue with K elements. If looking for the Kth largest element, use a min heap, so that peek (poll) from the priority queue returns the Kth element. If looking for the Kth smallest, use a max heap, so that peek (poll) from the priority queue returns the Kth element.
Related problems:
- 215: Kth Largest Element in an Array
- 378: Kth Smallest Element in a Sorted Matrix
- 703. Kth Largest Element in a Stream
- 973: K Closest Points to Origin
Use array as hash table. If possible, use an array as the reference table
for finding the right element. Compared to any Map implementation, using array
is faster and consumes less memory. This is typically possible when the keys are
ASCII characters. You can create an array with 128 elements, for boolean status
(boolean[]), char count (int[]), etc.
int[] counts = new int[128];
for (char c : word.toCharArray()) {
counts[c]++;
}Related problems:
Use Hashtable to Store References. Use hashtable to store the target references. It helps to reduce cost for lookup operation, compared to double for-loop.
Related problems:
2 pointers. One slow pointer (1x speed) and one fast pointer (2x speed). It allows to resolve circular issue, because the faster one will be 1 round faster after some moves. 2 pointers strategy can also be used for keeping a distance between two pointers.
Related problems:
Changing "next" reference. In sinlge linked list, changing the reference of the "next" node can be useful for some operations, such as reversing the list. Here is an illustration:
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 <- 2 <- 3 <- 4 <- 5
Related problems:
Two Pointers. Use two pointers L, R for switching characters.
Related problems:
Permutation in String. Maintain a sliding window [L, R] in the string, use
two variables: int[] stock and int todo to record respectively what are the
remaining characters available for permutation as ASCII table, and the remaining
number of characters to do to have a match.
- When R (right pointer) moves forward, it consumes more chars from the stock table.
- When L (left pointer) moves forward, it recover the consumed chars from the stock table.
Related problems:
- 3: Longest Substring Without Repeating Characters
- 76: Minimum Window Substring
- 438: Find All Anagrams in a String
- 567: Permutation in String
String construction. When resolving exercises, it's better to use
java.lang.StringBuilder
rather than string concatenation using +. Even better, use char array char[]
and fill it manually, which is efficient and allows navigation.
| Constructor | Description |
|---|---|
StringBuilder() |
Constructor without additional arguments |
StringBuilder(String) |
Constructor with an initial string |
StringBuilder(int) |
Constructor with initial capacity |
String(char[]) |
Constructor with a char array |
String(char[], int, int) |
Constructor with offset and length |
Power of Two. An integer is power of two if it is positive and has only one bit.
| N | Binary |
|---|---|
| 1 | ... 0000 0000 0000 0001 |
| 2 | ... 0000 0000 0000 0010 |
| 4 | ... 0000 0000 0000 0100 |
| 8 | ... 0000 0000 0000 1000 |
| 16 | ... 0000 0000 0001 0000 |
There are two types traverals: depth-first search (DFS) and breath-first search (BFS). For depth-first search, the traversal can be pre-order (NLR), in-order (LNR), out-order (RNL), and post-order (LRN).
Depth-first search: pre-order
Depth-first search: in-order
Depth-first search: post-order
Breath-first search:
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". Graph can be undirected or directed. The figure below shows an example network with 8 vertices and 10 edges.
Graph (undirected graph):
Directed Graph:
Dynamic programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. Remember the three steps:
- Defining sub-problems
- Finding recurrences
- Solving the base cases
For more detail, see Stanford University Online Lecture CS 97SI: https://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf.
Enrich Integer Via Bits. You can provide additional information to an integer by using the unused bits. This is possible when integer is served as an emumerate value, e.g. only using 0 as false and 1 as true. This strategy is useful when you need to do something in-place, or you are not allowed to use more complex data structure.
Related problems:
Custom Binary Search. In some cases, the problem can be solved by using a binary-search-like strategy to find the target item by eliminating half of the items.
Related problems:
LRU Cache. Discards the least recently used items first. See YouTube video Implement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode) for more detail explanation.
Related problems:
Useful APIs in Java.
| Method | Description |
|---|---|
String(char[] value, int offset, int count): String |
String constructor, useful for creating a string from a char array. |
String#substring(int beginIndex, int endIndex): String |
Extracts a substring from string. |
TreeNode:
- Can
rootbenull?
Integer:
- Boundaries:
Integer.MIN_VALUEandInteger.MAX_VALUEgood boundaries? Comparison will fail when the integer itself is one of these values. - Risk of overflow?
- Average for sum of two integers: prefer
start + (end - start) / 2rather than(start + end) / 2, so that the overflow problem can be avoided. - Integer division: when both dividend and divisor are integer, the
quotient will be an integer too. For example,
3 / 2 = 1. In order to have an accurate result, you need to ensure either divident or divisor to be a float or a double.
Array:
- Can array be null?
- The length of the array?
- Subarray: how to define subarray, at least 1 item or 2 items?
2D Array:
- Coordinate (x, y) or (i, j): which position is (0, 0), what direction is the axes? It's easy to draw diagram on whitebroad using (x, y) like in Math. But in the program, it's easier to use (i, j).
Comparator:
- Compare one field after another, if one field is different, compute the diff and return the result. Only when this field is equal on both instances, you can pass to the next field. Be careful about problem "Comparison method violates its general contract!"
Too lazy to add 🙈
- Oracle, "String (Java Platform SE 8)", Oracle Documentation, 2019. https://docs.oracle.com/javase/8/docs/api/java/lang/String.html
- Jaehyun Park Ph.D., "Dynamic Programming - CS 97SI", Stanford University, 2015. https://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf
- Wikipedia, "Cache replacement policies", Wikipedia, 2019. https://en.wikipedia.org/wiki/Cache_replacement_policies
- Wikipedia, "Graph (discrete mathematics)", Wikipedia, 2019. https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
- Wikipedia, "Permutation - Generation in lexicographic order", Wikipedia, 2019. https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
- Wikipedia, "Prefix sum", Wikipedia, 2019. https://en.wikipedia.org/wiki/Prefix_sum
- Wikipedia, "Tree traversal", Wikipedia, 2019. https://en.wikipedia.org/wiki/Tree_traversal
- Wikipedia, "Vertex (graph theory)", Wikipedia, 2019. https://en.wikipedia.org/wiki/Vertex_(graph_theory)
- Back To Back SWE, "Implement An LRU Cache - The LRU Cache Eviction Policy (LRU Cache on LeetCode)", YouTube, 2019. https://www.youtube.com/watch?v=S6IfqDXWa10