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. ⚠️ Make sure they stop at the right moment to avoid collapse.

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:

• 31. Next Permuation

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:

• 974: Subarray Sums Divisible by K

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:

• 771: Jewels and Stones

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:

• 1: Two Sum
• 560: Subarray Sum Equals K

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:

• 19. Remove Nth Node From End of List

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:

• 92: Reverse Linked List II
• 206: Reverse Linked List

Two Pointers. Use two pointers L, R for switching characters.

Related problems:

• 344: Reverse String

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.

Power of Two. An integer is power of two if it is positive and has only one bit.

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:

1. Defining sub-problems
2. Finding recurrences
3. 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:

• 289: Game of Life

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:

• 378. Kth Smallest Element in a Sorted Matrix

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:

• 146: LRU Cache

Useful APIs in Java.

TreeNode:

• Can root be null?

Integer:

• Boundaries: Integer.MIN_VALUE and Integer.MAX_VALUE good 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) / 2 rather 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