Algorithmic Toolbox

Description

This post documents basic, but important algorithmic techniques for solving computational problems and building box for real world problems.

String

Reverse a string

Swap characters

  • $O(n)$ time, $O(1)$ space

Stack

  • $O(n)$ time, $O(n)$ space

Integer

reverse an integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int reverse(int x) {
int rev_num = 0;
while (x != 0) {
int digit = x % 10;

/ ******* this part handle overflow **********./
int pre_rev_num = rev_num;
/ ******* this part handle overflow **********./

rev_num = rev_num * 10 + digit; // [X]

/ ******* this part handle overflow **********./
// observation: if rev_num NOT overflow after [rev_num * 10 + currentDigit]
// (rev_num - digit) / 10 should == pre_rev_num
if ((rev_num - digit) / 10 != pre_rev_num) {
return 0;
}
/ ******* this part handle overflow **********./

x /= 10;
}
return rev_num;
}

Second approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
reverse(int x) {
int rev_num = 0;
while (x != 0) {
int digit = x % 10;
// check for overflow
if (rev_num > Integer.MAX_VALUE || (rev_num == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10) {
// overflow
}
rev_num = rev_num * 10 + digit;
x /= 10;
}

}

detect overflow

  • TODO: 32bit cpu 64bit register

Linked List

Reverse linked list

http://xuyiruan.com/2018/02/04/reverse-linked-list/

iterative O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;

while (head != null) {
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}
}

recursive O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public ListNode reverseList(ListNode head) {
// if given head is null, return null
// head.next = null detect last node
if (head == null || head.next == null) {
return head;
}

// recursive to second to the last node in linked list
ListNode pre = reverseList(head.next);
// where 'pre' always point to the end node, which was pass back into recursive call
head.next.next = head;
head.next = null;

return pre;
}
}

iterative O(n) space w/stack

http://blog.csdn.net/crazy1235/article/details/66971177

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}

Deque<ListNode> stack = new ArrayDeque<ListNode>();

while (head != null) {
stack.push(head);
head = head.next;
}

ListNode newHead = stack.peek();
while (!stack.isEmpty()) {
ListNode curr = stack.pop();
curr.next = stack.isEmpty() ? null : stack.peek();
}

return newHead;
}
}

Merge two sorted linked list [x]

lesson learned:

  • try dummy node to generalize special case handling. (use dummy to eliminate special case handling, perform general algorithm directly)

dummy helps to

  1. remember head of linkedlist, also
  2. generalize algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // important technique
ListNode lastNode = dummy;
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}

while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
lastNode.next = l1;
l1 = l1.next;
} else {
lastNode.next = l2;
l2 = l2.next;
}
lastNode = lastNode.next;
}

if (l1 == null) {
lastNode.next = l2;
} else {
lastNode.next = l1;
}

return dummy.next;
}
}

ref: https://leetcode.com/problems/merge-two-sorted-lists/description/

Detect cycle in linked list

ver1:

  • return true or false
  • $O(n)$ space HashSet
  • $O(1)$ space w/ two pointers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// two pointers
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}

ListNode slow = head;
ListNode fast = head; // [X] fast = head.next also works here, but inf look in detect cycle 2 below

while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;

}
return false;
}

https://leetcode.com/problems/linked-list-cycle/description/

Note: think about why will slow and fast pointer always meet if there is a cycle?

ver2:

  • return node where the cycle begins
  • $O(n)$ space HashSet
  • $O(1)$ space w/ two pointers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head; // [X]
// dont use fast = head.next, it cuases inf loop when 1->2-> back to 1

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}

if (fast == null || fast.next == null) {
return null;
}

slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}

https://leetcode.com/problems/linked-list-cycle-ii/description/

key observation: the distance d1, from location where slow and fast pointer meet to the start of the cycle is exactly the same distance d2, from head to the begining of the cycle. why? TODO:

876. Middle of the Linked List

Note: when array size if even, there are two possible mid value: first mid value & second mid value.

When need the second middle node, which is slightly different. we have fast = head.

1
2
[1,2,3,4,5] returns 3
[1,2,3,4] returns 3
1
2
3
4
5
6
7
8
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

When returns first of middle node, only difference is fast = head.next:

1
2
[1,2,3,4,5] returns 3
[1,2,3,4] returns 2
1
2
3
4
5
6
7
8
9
public ListNode middleNode(ListNode head) {
if (head == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

ref: https://leetcode.com/problems/middle-of-the-linked-list/discuss/154635/Java-5-Liner-with-explanations

Search Algorithms

  • sorted array only
  • time: $O(logN)$
  • space: $O(1)$

binary search v1: iterative (preferred)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int mid = 0;
int right = nums.length - 1;
while (left + 1 < right) {
// [X] dont forget `()` for shift op
mid = left + ((right - left) >> 1); // >> arithmetic right shift
if (nums[mid] == target) return mid;
if (target < nums[mid]){
right = mid - 1; // [X] -1 only if 100% sure sol not at num[mid]
} else {
left = mid + 1; // [X] +1 only if 100% sure sol not at num[mid]
}
}

if (nums[left] == target) {
return left;
}
if (nums[right] == target) {
return right;
}
return -1;
}

binary search v1: recursive

1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearch(int left, int right, int target, int[] nums) {
if (left + 1 >= right) {
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}

int mid = left + ((right - left) >> 1);
if (nums[mid] == target) return mid;
if (target < nums[mid]) return binarySearch(left, mid-1, target, nums);
else return binarySearch(mid+1, right, target, nums);
}

binary serach v2: iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int binarySearch(int[] nums, int target) {
// write your code here
if (nums == null || nums.length == 0) {
return -1;
}

int left = 0;
int mid = 0;
int right = nums.length - 1;

while (left <= right) { // when target is ON right pointer
mid = left + ((right - left) >> 1); // >> arithmetic right shift
if (nums[mid] == target) return mid;
if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}

Tree Traversal

DFS: pre-order traversal, recurssion (traverse)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
private void getValue(TreeNode root, ArrayList<Integer> list) {
// base case
if (root == null) {
return;
}

list.add(root.val);
getValue(root.left, list);
getValue(root.right, list);
}

DFS: pre-order traversal, iterative w/ stack [X]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Preorder in ArrayList which contains node values.
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> preorder = new ArrayList<Integer>();
if (root == null) {
return preorder;
}
stack.push(root);
while (!stack.empty()) {
TreeNode curr = stack.pop();
preorder.add(curr.val);
// LIFO / FILO
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
return preorder;
}
}

DFS: in-order traversal, recursion (traverse)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
private void getValue(TreeNode root, ArrayList<Integer> list) {
// base case
if (root == null) {
return;
}

getValue(root.left, list);
list.add(root.val);
getValue(root.right, list);
}

DFS: in-order traversal, iterative w/ stack [X]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
// write your code here
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> inorder = new ArrayList<Integer>();

TreeNode curr = root;
// curr != null in outter while loop allows empty stack enter while loop
// case when far_left_node.right == null
while (curr != null || !stack.empty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
inorder.add(curr.val);
curr = curr.right;
}
return inorder;
}
}

DFS: post-order traversal, recursion (traverse)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
private void getValue(TreeNode root, ArrayList<Integer> list) {
// base case
if (root == null) {
return;
}

getValue(root.left, list);
getValue(root.right, list);
list.add(root.val);
}

DFS: post-order traversal, iterative [X]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root == null) return ans;

stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val); // [X]
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
}

DFS: post-order traversal, iterative (w/ Deque & Guide helper) [X]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {

List<Integer> result = new ArrayList<>();
Deque<Guide> stack = new ArrayDeque<>(); // deque is faster
stack.addFirst(new Guide(0, root));

while (!stack.isEmpty()) {
Guide guide = stack.removeFirst();
if (guide.node == null) { // defensive coding
continue;
} else if (guide.op == 1) {
result.add(guide.node.val);
} else {
// visit root.left
// visit root.right
// print root.val

stack.addFirst(new Guide(1, guide.node));
stack.addFirst(new Guide(0, guide.node.right));
stack.addFirst(new Guide(0, guide.node.left));
}
}

return result;
}

private class Guide {
int op; // 0: visit 1: print
TreeNode node;

public Guide(int op, TreeNode node) {
this.node = node;
this.op = op;
}
}
}

BFS: level-order traversal

1 Queue version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/


public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public List<List<Integer>> levelOrder(TreeNode root) {
// write your code here
Deque<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> currLevel = new ArrayList<>();
int size = queue.size();

for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
currLevel.add(curr.val);

if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
}
result.add(currLevel);
}
return result;
}
}

Graph Algorihtm

Topological Sort

  • linear ordering of vertices in Directed Acyclic Graph (DAG)
  • edges may represent constraints for one task must be performed before another
  • scheduling problem

Kahn’s algorithm

  • step1: initialize graph (ArrayList[] graph = new ArrayList[size])
  • step2: build graph & compute incoming edges
  • step3: push node with 0 incoming edges into queue
  • step3: apply Kahn’s algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// pseudo code

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do (JAVA: S = queue)
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph (JAVA: inDegree[node] -= 1)
if m has no other incoming edges then (JAVA: inDegree[node] == 0)
insert m into S (JAVA: S = queue)
if graph has edges then (JAVA: if has node where inDegree[node] != 0)
return error (graph has at least one cycle)
else
return L (a topologically sorted order)

https://leetcode.com/problems/course-schedule-ii/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int[] inEdges = new int[numCourses];
List<List<Integer>> graph = new ArrayList<List<Integer>>(numCourses);

Queue<Integer> queue = new LinkedList<>();
Queue<Integer> result = new LinkedList<>();

// initialize graph
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<Integer>());
}

// build graph & compute incoming edges
for (int[] edge : prerequisites) {
int startNode = edge[1];
int endNode = edge[0];

inEdges[endNode] += 1;
graph.get(startNode).add(endNode);
}

int count = 0;
// push node with 0 incoming edges into queue
for (int i = 0; i < inEdges.length; i++) {
if (inEdges[i] == 0) {
queue.offer(i);
}
}

// apply BFS topo sort algorithm
while (!queue.isEmpty()) {
int n = queue.poll();
result.offer(n);
count++;
for (Integer i : graph.get(n)) {
int index = (int)i;
inEdges[index] -= 1; // # of prerequisite for node [idx]
if (inEdges[index] == 0) { // prerequisite all finish
// queue.offer(i);
queue.offer(index);
}
}
}
// cycle will NOT be explored since inEdge != 0, node in cycle will NOT be pushed into process queue
// numCourses > count
if (numCourses > count) { // [X] cycle start node will not be pushed into queue, hence count < numCourses detect cycle
// cycle detect
return new int[0];
}

Topological sort only work for DAG (Directed Acyclic Graph)

ref: https://en.wikipedia.org/wiki/Topological_sorting

Union Find

  • create UnionFind Object UnionFind uf = new UnionFind();
  • init id=i, and size=1 arrays
  • union() if find(p,q) == false
  • count is the number of connected components
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class UnionFind {
int[] id; // find its parent, init to self in main code, OR -1 to check if has been visited
int[] size; // determine which groups to merge to, init to 1 in main code
int count; // num of connected component

public UnionFind(int len) {
this.id = new int[len];
this.size = new int[len];
this.count = len;
}

public boolean find(int p, int q) {
return root(p) == root(q);
}

public void union(int p, int q) {
int pi = root(p), qi = root(q); // connect pi(root) and qi(root), path compress so that p,q directly connect to the root
if (this.size[pi] < this.size[qi]) {
this.id[pi] = qi;
this.size[qi] += this.size[pi];
} else {
this.id[qi] = pi;
this.size[pi] += this.size[qi];
}
count--;
}

public int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]]; // path compression
i = id[i];
}
return i;
}
}

source: xcode career service

usage examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// how to set `uf.id` base on application
// application to set uf.id = -1 to mark unvisited element

public List<Integer> numIslands2(int m, int n, int[][] positions) {
UnionFind set = new UnionFind(m * n);
Arrays.fill(set.id, -1); // -1 means not visited
...
for (int[] position : positions) {
int x = position[0], y = position[1];
int index = x * n + y;
...
set.id[index] = index; // set root to itself
...
}

// other application did set uf.id = i
public int countComponents(int n, int[][] edges) {
UnionFind u = new UnionFind(n);
for (int i = 0; i < n; i++) {
u.id[i] = i;
}
for (int[] e : edges) {
if (!u.find(e[0], e[1])) {
u.union(e[0], e[1]);
}
}
return u.count;

Minimum Spanning Tree (MST)

  • 图论中比较重要的模型, 解决实际生活中的路径代价最小一类的问题
  • MST 问题有两种解法: Prim算法 和 Krushal算法+Union Find Set
  • MST works on weighted undirected connected graph (directed graph requires modification)
  • Prim 算法: 基于点的算法,适合dense graph
  • Krushal算法: 基于边的算法,适合sparse graph
  • applications:
    • telecommunications companny trying to lay cable in a new neighborhood with minimum cost of connecting all houses
    • city tries to construct new road which connected major cities with lowest costs
      • topology of chip plancement of MOSFET, etc (simulated annealing)
  • subsets of the edges of a connected, weighted undirected graph that connects all the vertices together
  • MST contains no cycles
  • the sum of all edges is at mininum
  • minimum spanning forest, is simliar, but nodes are not necessary connected
  • MST 和 Union Find 的联系
    • MST 算法中重要一步是判断newly added edge会不会造成cycle
    • 可以使用DFS/BFS,但是每次加入新edge后,重新dfs的time complexity 很高
    • 因此我们可以使用union find结构去快速(log(V) vs dfs O(V))的查找新edge是否会造成cycle
    • 感谢!ref: https://www.cnblogs.com/luruiyuan/p/5528406.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class MST {
/**
* Kruskal's algorithm = MST algorithm + disjoint-set data structure
*
*/
static class DisjointSet {
Map<String, String> map;
int count;

public DisjointSet() {
this.count = 0;
this.map = new HashMap<>();
}

public void makeSet(String s) {
if (this.map.containsKey(s)) {
return;
}
this.count++;
this.map.put(s, s);
}

// recursive way
public String root2(String k) {
String v = this.map.get(k);
if (v == null) {
return null;
}

if (k.equals(v)) {
return k;
}
String root = this.root(v);
this.map.put(k, root); // path compression
return root;
}

// iterative way
private String root(String k) {
String v = this.map.get(k);
if (v == null) {
return null;
}
while (!v.equals(k)) {
String oldKey = k;
k = v;
v = this.map.get(k);
this.map.put(oldKey, v); // path compression
}
return k;
}

public void union(String s, String t) {
if (!this.map.containsKey(s) || !this.map.containsKey(t)) {
return;
}
if (s.equals(t)) {
return;
}
this.count--;
/**
* 4 -> 5, add 1-4 connection
* if s=1, t=5: 4 -> 5, 5 is root of all nodes
* ^
* |
* 1
*
* if s=5, t=1: 4 -> 5 -> 1, 1 became the root, but all three nodes still within the SAME component
*
*/
this.map.put(s, t); // who become root is NOT important, as long as all nodes in the SAME connected component
}

public static void main(String[] args) {
// 1. init makeSet() for each set
// 2. union if disjoint set did not share root
// 3. add connection as part of MST
// 4. MST complete when count == 1
}
}
}

Sort Algorithms

quick sort (Hoare partition scheme)

  • time: $O(nlogn)$ best case, $O(n^2)$ worst case in time
  • space: $O(1), but $$O(logN)$ space (call stack), worst case $O(N)$ where array already sorted
  • NOT a stable sort algorithm
  • cache efficient (Quicksort accesses continuos elements during algorithm)

Just for fun 博主《被忽视的 partition 算法》一文对partiton算法进行了深入的研究,提供的partition算法 1. 更加高效(删去了swap 方程中tmp的使用,每一次的swap减少了一次的拷贝)2. 更加简洁 (代码量更少)3. 更容易解释算法每一步的用途(解决了v2中 right, left, 和pivot位置都是模糊点,v1对此可以清晰的解释)。有时间再仔细研究Partition 进阶算法部分(TODO)。

v1 (preferred)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void quickSort(int[] arr, int l, int r) {
if (l < r) { // l == r 已经没必要partition了
int mid = partition(arr, l, r);
quickSort(arr, l, mid - 1); // mid the piviot idx, which alreay in its pos, hence mid - 1
quickSort(arr, mid + 1, r); // mid the piviot idx, which alreay in its pos, hence mid + 1
}
}

public static int partition(int[] arr, int l, int r) {
int pivot = arr[l]; // 首元素作pivot
while (l < r) {
while (l < r && arr[r] >= pivot) r--; // pivot can be at either side of the piviot, further parition will put val the same as pivot into place
arr[l] = arr[r];
while (l < r && arr[l] <= pivot) l++; // pivot can be at either side of the piviot, further parition will put val the same as pivot into place
arr[r] = arr[l];
}
arr[l] = pivot; // 此时 l == r, arr[l] == arr[r] 已备份,因此pivot可以复写arr[l]
return l; // l == r after break from while()
}

example problem using the partition alogrihtm: https://leetcode.com/problems/k-closest-points-to-origin/

v2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public Random rand;
public void sortIntegers2(int[] A) {
rand = new Random();
// write your code here
quickSort(A, 0, A.length - 1);
}

public void quickSort(int[] A, int start, int end) {
if (start >= end) return; // [X]
int p = hoare_partition(A, start, end);
quickSort(A, start, p);
quickSort(A, p + 1, end);
}

public int hoare_partition(int[] A, int start, int end) {
// key1: rand.nextInt(2) returns [0, 1]
int index = rand.nextInt(end - start + 1) + start;
// int index = start + ((end - start) >> 1);
// key2: pivot is A[index]
int pivot = A[index];
int left = start;
int right = end;

// key3: NOT left < right, because want [right, left] postion after while loop
// where right + 1 = left
while (left <= right) { // [X]
// key4: NOT A[left] <= pivot
while (left <= right && A[left] < pivot) { // left <= right is required to prevent indexOutOfBound exception by `A[left]`
left++;
}
while (left <= right && A[right] > pivot) {
right--;
}

if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;

left++;
right--;
}
}
return right; // [X]
// // A[start... right]
// quickSort(A, start, right);
// // A[left ... end]
// quickSort(A, left, end);
}

ref: http://www.jiuzhang.com/solutions/quick-sort

merge sort

  • time: $O(nlogn)$ worst/best case in time
  • space: $O(n)$ space
  • stable sort algorithm
  • cache inefficient (mergesort which accesses distant elements in the merge routine)

Note: In java, it uses Merge Sort for sorting Arrays of Objects. This is because, merge sort is stable, so it won’t reorder elements that are equal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class MergeSort {
public static void main(String[] args) {
int[] array = {5, 5, 4, 3, 1, 3, 1, 0, 5};
int[] temp = new int[array.length];
mergeSort(array, 0, array.length -1, temp);
}
public static void mergeSort(int[] array, int start, int end, int[] temp) {
if (start >= end) return;
int mid = start + (end - start) / 2;
mergeSort(array, start, mid, temp);
mergeSort(array, mid+1, end, temp);
merge(array, start, mid, end, temp);
}

public static void merge(int[] array, int start, int mid, int end, int[] temp) {
int i = start; // [X]
int j = mid+1; // [X]
int k = 0; // [X]
while (i <= mid && j <= end) { // [X]
if (array[i] <= array[j]) {
temp[k++] = array[i++]; // [X] i++
} else {
temp[k++] = array[j++]; // [X] j++
}
}
while (i <= mid) {
temp[k++] = array[i++];
}
while (j <= end) {
temp[k++] = array[j++];
}
for (int v = 0; v < k; v++) {
array[v+start] = temp[v];
}
}
}

Queue

Queue Initialization

update: 05/30/2018

1
2
// preferred, faster wo/ object initialization
Deque<Integer> queue = new ArrayDeque<>();

Important note: ArrayDeque throws NullpointerException upon adding null to the queue. If supporting null element is necessary, use LinkedList implementation instead.

Using ArrayDeque is faster as implementation for Queue. As mentioned in Java doc:

ArrayDeque class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
ref: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html

1
2
3
// java
Queue<Integer> queue = new LinkedList<>();
Queue<Integer> queue2 = new PriorityQueue<>();

Min Heap & Max Heap

  • PriorityQueue is the implementation of min-heap and max-heap in Java
  • default PriorityQueue is a min-heap
  • modify comparator for max-heap
1
2
3
4
5
6
7
8
9
// minheap
public int compare(int a, int b) {
return a - b; // be aware of overflow
}

// maxheap
public int compare(int a, int b) {
return b - a; // be aware of overflow
}

Min-heap & Max-Heap in Java https://stackoverflow.com/a/20559263

Modify compare() for max-heap

Arithmetic:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Queue <ListNode> maxQueue = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2){

// method 1: if for sure no overflow
return o2.val - o1.val;

// method 2: [preferred]
return Integer.compare(o2.val, o1.val);

// method 3:
if (o2.val < o1.val) {
return -1;
} else if (o1.val == o2.val) {
return 0;
} else {
return 1;
}
}
});

Note: Comparator is an interface, new Comparator() above is using anonymous class. An anonymous class is a local class without a name, which implements the Comparator() interface. Hence, we create an instance of the annoymous class.

ref: https://stackoverflow.com/questions/20725044/new-keyword-with-comparator-interface

Lambda Expression (preferred)

1
2
3
4
5
PriorityQueue<Map.Entry<String, Integer>> max_pq = new PriorityQueue<>(
// no return: implicit return
// no semicol
(a,b) -> b.getValue() - a.getValue() // [X] make sure no overflow
);

Note:
The contructor above uses contructor PriorityQueue(Comparator<? super E> comparator) where Comparator is an interface. Since Comparator is a functional interface, which means there is only ONE unimplemented funtion compare(). Hence we can use lambda exp as instances of single-method classes for implementing the Comparator interface.

Comparator Interface(preferred)

Comparator is an interface, all implemented class need to create ALL abstract methods within the interface. Before Java 8, there are 18 abstract methods (method without body), which means any class implements the interface requires to implements ALL 18 methods.

After Java 8, the defintion of functional interface emerged. A functional interface is a interface with only ONE abstract method to implement. For Comparator functional interace, the only unimplmented abstract method is comapre(T o1, T o2). equals() method even though seems like unimplemnted, but it inherited from Object class. The rest of 16 methods are all default methods with pre-implemented body.

ref: https://coderanch.com/t/666875/java/Comparator-interface-java-functional-interface

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class PointComparator implements Comparator<int[]> {
@Override
public int compare(int[] p1, int[] p2) {
return (p2[0] * p2[0] + p2[1] * p2[1]) - (p1[0] * p1[0] + p1[1] * p1[1]);
}
}

// 2. max heap maintains size K
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(K, new PointComparator());
for (int[] point : points) {
maxHeap.offer(point);
if (maxHeap.size() > K) {
maxHeap.poll();
}
}
int[][] res = new int[K][2];
while (!maxHeap.isEmpty()) {
res[--K] = maxHeap.poll();
}
return res;
}

Comparator object via anonymous class:

1
2
3
4
5
6
7
8
9
10
// class variable
private Comparator<ListNode> compare = new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return b.val - a.val;
}
}; // semicolon to end a variable declaration

public void getTopK() {
Queue<ListNode> maxQueue = new PriorityQueue<>(queue.size(), compare);
}

PriorityQueue & Map.Entry doc
https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
https://docs.oracle.com/javase/7/docs/api/java/util/Map.Entry.html

priority queue application:
https://leetcode.com/problems/merge-k-sorted-lists/description/

LC692 Top K Frequent Words

Min-heap implementation (nlogK) [less time]
https://leetcode.com/problems/top-k-frequent-words/discuss/108346/My-simple-Java-solution-using-HashMap-and-PriorityQueue-O(nlogk)-time-and-O(n)-space/136123?page=1

Max-heap implementation (nlogn)
https://leetcode.com/problems/top-k-frequent-words/discuss/108346/My-simple-Java-solution-using-HashMap-and-PriorityQueue-O(nlogk)-time-and-O(n)-space/119001
https://leetcode.com/problems/top-k-frequent-words/discuss/108359/Java-HashMap-and-MaxHeap-O(nlogn)

Recursion Alogorithm

TODO

Dynamic Programming

TODO

Math

  • Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers
1
2
3
4
5
6
7
8
9
10
11
12
find GCD(3000, 197) using Euclid Algorithm

3000 = 15(197) + 45
197 = 4(45) + 17
45 = 2(17) + 11
17 = 1(11) + 6
11 = 1(6) + 5
6 = 1(5) + 1

hence, finding GCD(3000, 197) is equivalent to:

GCD(3000, 197) -> GCD(197, 45) -> GCD(45, 17) -> ... -> GCD(5, 1) = 1

Note: a number has inverse modulo N only if GCD(x, N) = 1

https://www.youtube.com/watch?v=mgvA3z-vOzc

greatest common divisor (gcd) [X]

1
2
3
4
int gcd(int a, int b) {
if (a == 0) return Math.abs(b);
return gcd(b % a, a);
}

geast common multiple (lcm)

1
2
3
int lcm(int a, int b) {
return a * b / gcd(a, b);
}

check prime number

1
2
3
4
5
6
7
public boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}

Further optimzation (skip even number):

1
2
3
4
5
6
7
8
public boolean isPrime(int n) {
if (n <= 1) return false;
if (n > 2 && (n & 1) == 0) return false;
for (int i = 3; i <= Math.sqrt(n); i += 2) {
if (n % i == 0) return false;
}
return true;
}

factorial computation

1
2
3
4
5
6
7
8
static long fact(int n) {
// n! = n * (n-1) * ... * 2 * 1
long f = 1;
for (int i = 2; i <= n; i++) {
f = f * i; // all math is done in the largest data type in java
}
return f;
}

int multiple long in java: https://stackoverflow.com/questions/1494862/multiplying-long-values

fib()

TODO:

permutation

$$p(n, k) = \frac{n!}{(n-k)!}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class StringPermutation {
public static void main(String[] args) {
String string = "123";
permutate(string, 0);
}
public static void permutate(String string, int currentIdx) {
if (currentIdx == string.length() - 1) {
System.out.println(string);
}
for (int i = currentIdx; i < string.length(); i++) {
StringBuilder newString = new StringBuilder(string);
char temp = newString.charAt(currentIdx);
newString.setCharAt(currentIdx, newString.charAt(i));
newString.setCharAt(i, temp);
permutate(newString.toString(), currentIdx+1);
}
}
}

ref: http://xuyiruan.com/2018/03/11/permutation-and-combination/

combination

$$c(n, k) = \frac{n!}{(n-k)!k!}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.ArrayList;
import java.util.List;

public class StringCombination {
public static void main(String[] args) {
String string = "12345";
List<String> result = combination(3, string);
for (String str : result) {
System.out.println(str);
}
}

public static List<String> combination(int k, String string) {
int n = string.length();
List<String> result = new ArrayList<>();

if (k == 0) { // IMPORT: k = 0 when no more to select
result.add("");
return result;
}
// when k == n
if (k == n) {
result.add(string);
return result;
}

for (int i = 0; i < n-k+1; i++) {
char currentChar = string.charAt(i);
List<String> temp = combination(k-1, string.substring(i+1));
for (String tempStr : temp) {
result.add(currentChar + tempStr);
}
}
return result;
}
}

ref: http://xuyiruan.com/2018/03/11/permutation-and-combination/

Detect Overflow

1
2
3
4
5
// assume next step: num * 10;

if (Integer.MAX_VALUE / 10 < num || (Integer.MAX_VALUE / 10 == num && Integer.MAX_VALUE % 10 < digit)) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}

Others

List Initalization

1
2
3
// java
List<String> list = new ArrayList<>();
List<String> list2 = new LinkedList<>();

HashMap Initialization

1
2
// java
Map<String, Integer> map = new HashMap<>();

Stack Initialization

1
2
// Old way
Stack<Integer> stack = new Stack<>();
1
2
3
4
5
6
// new way
Deque<Integer> stack = new ArrayDeque<Integer>();
stack.push(); // will call addFirst()
stack.pop(); // will call removeFirst()
stack.peek(); // will call peekFirst()
stack.isEmpty(); // isEmpty()

Stack has been depreciated

javadoc: ArrayDeque class is likely to be faster than Stack when used as a stack https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html

Queue Initialization

1
2
// old way
Queue<Integer> queue = LinkedList<Integer>();
1
2
3
4
5
6
7
// new way
Queue<Integer> queue = ArrayDeque<Integer>();
Deque<Integer> queue = ArrayDeque<Integer>();

queue.add(); // will call addLast()
queue.remove(); // will call removeFirst()
queue.peek(); // will call peekFirst()

https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

Deque source code:
https://zhuanlan.zhihu.com/p/24752167
Benefits of ArrayDeque:
http://www.baeldung.com/java-array-deque

Java Collection Framework

  • An interface can extend multiple interfaces.
  • A class can implement multiple interfaces.
  • However, a class can only extend a single class.

src: https://stackoverflow.com/a/19546440

TODO: Java-Collection Framework学习要点 https://blog.csdn.net/zolalad/article/details/11368561

Exception Handling

common type of exceptions:

  • IllegalArgumentException
  • NullPointerException
  • ArithmeticException
  • RuntimeException
  • IOException
  • IndexOutOfBoundsException

throw exception

1
2
3
4
if (numStudents <= 0) {
throw new IllegalArgumentException(“Number of “ + “ students is 0”);
}
avgGrade = total / numStudents;

try/catch block

1
2
3
4
5
6
try {
...

}catch(IllegalArgumentException e) {
e.printStackTrace();
}

finally block

  • The statements present in this block will always execute regardless of whether exception occurs or not.
  • usually put clean-up code within finally block (etc, close IO, close a connection, etc).
1
2
3
4
5
6
7
8
9
10
try {
...

} catch (IllegalArgumentException e) {
e.printStackTrace();
} finally {
// clean-up code goes where
// always got execute disregard of whether or not error occour.

}

checked vs unchecked exception

checked exception:

  • type of exception programmer must handle, otherwise, it will NOT compiled
  • know before run-time

unchecked:

  • type of exception prgrammer not required to handle, complie without error. If exception found, use throw new Exception without catching it.
  • usually runtime error

Optimization

micro-optize

1
2
3
4
5
6
7
8
9
10
11
12
13
// method 1: 
if (o1.val < o2.val) {
return -1;
} else if (o1.val == o2.val) {
return 0;
} else {
return 1;
}

// method 2: return Integer.compare(o1.val, o2.val);

// method 3: if for sure no overflow
// return o1.val - o2.val;

in theory, method 1 is most optimized even it has the most line of code. Method 2 is less optimized since it creates unnecessary Integer objects, where Integer.compare(o1.val, o2.val) compiles to Integer.valueOf(o1.val).compareTo(Integer.valueOf(o2.val)).

However, the above optimziation is called micro-optimization, unless it was measured/profiled it suffer from peroformance issue, we tend to avoid this kind of micro-optimation.

ref: https://stackoverflow.com/questions/9150446/compareto-with-primitives-integer-int

HashMap clean code

  • map.getOrDefault()
  • map.computeIfAbsent()
  • map.putIfAbsent()

update: 05/30/2018

when counting the number of time a key appear in a dictionary, we usually need to check if current key exists:

1
2
3
4
5
6
7
Map<Integer, Integer> map = new HashMap<>();

if (map.containsKey(key)) {
map.put(key, map.get(key) + 1);
} else {
map.put(key, 1);
}

Above code could be simplify with getOrDefault(key, 0) api:

1
map.put(key, map.getOrDefault(key, 0) + 1); // [X]

Similiary, computeIfAbsent() solve key not found upon map.get(key):

1
2
3
map.computeIfAbsent(key, k -> new HashSet<V>()).add(v);
// if key exists, return its val, then perform `add(v)`
// if key not exists, perform `map.put(k, new HashSet<V>())`, then perform `add(v)`

decrement value of given key

map.put(key, map.get(key) - 1);
if (map.get(key) == 0) {
    map.remove(key);
}

Logs

03/13/2018:

  • add prioityQueue override compare method,
  • add micro-optimization
  • add merge two sorted linked list
  • add permutation & combination code
  • add front cover
  • 03/17/18: refactor code for quick sort
  • 03/17/18: add topological sort
  • 03/17/18: fix quick sort bug
  • 04/21/18: add cycle detection in linkedlist
  • 04/23/18: add Euclid’s algorithm for finding GCD
  • 05/01/18: add reverse string
  • 05/01/18: updated quicksort algorithm
  • 05/07/18: added priorityQueue in Java (min/max heap)
  • 05/09/18: add code for topo sort
  • 05/10/18: add iterative post-order traversal
  • 05/10/18: add detect overflow
  • 05/30/18: mark [X] requires more attention
  • 05/30/18: add getOrDefault() for hashMap
  • 04/30/19: update functional interface
  • 04/30/19: add v1 partition alogirhtm for quicksort
  • 05/09/19: fix typo, update contents
  • 09/02/19: add factorial code block
  • 09/07/19: more example for union find usage
  • 09/07/19: add more details for MST

ref

front cover image: http://wvbadbuildings.org/resources/tools/all-bad-building-tools/
https://www.coursera.org/learn/algorithmic-toolbox