Algorithm templates
Table of Contents
Sorting⌗
3-way quick sort⌗
// [l, r)
void sort(int[] arr, int l, int r) {
if (l > r) return;
int i = l, j = r;
int t = l;
int pivot = arr[l + (r - l) / 2] // or arr[l + random.nextInt(r - l)];
while (t <= j) {
if (arr[t] < pivot) {
swap(arr, t++, i++);
} else if (arr[t] > pivot) {
swap(arr, t, j--);
} else {
t++;
}
}
//
// After t > j we can partition arr to [L L L L L L L L | E E E E E E E | G G G G G G G G G ]
// l i j r
// L: Number that less than pivot
// E: Number that equals to pivot
// G: Number that greater than pivot
//
sort(arr, l, i - 1);
sort(arr, j + 1, r);
}
Exercises:
- LC 75.Sort Colors
- LC 1356.Sort Integers by The Number of 1 Bits
- LC 1636.Sort Array by Increasing Frequency
- LC 1122.Relative Sort Array
- LC 2191.Sort the Jumbled Numbers
- LC 905.Sort Array By Parity
Quick Select⌗
private int[] kth(int[][] arr, int l, int r, int k) {
if (l == r) return arr[l];
int i = l, j = r;
int t = l;
int[] pivot = arr[(l + r) >> 1];
while (t <= j) {
if (compareTo(arr[t], pivot) < 0) {
swap(arr, i++, t++);
} else if (compareTo(arr[t], pivot) > 0) {
swap(arr, j--, t);
} else {
t++;
}
}
if (i - l >= k) {
// k
// L L L L L L E E E E E G G G G G G G
// i j
return kth(arr, l, i - 1, k);
} else if (j - l + 1 < k) {
// k
// L L L L L L E E E E E G G G G G G G
// i j
return kth(arr, j + 1, r, k - (j - l + 1));
} else {
return pivot;
}
}
Exercises:
- LC 1387.Sort Integers by The Power Value
- LC 973.K Closest Points to Origin
- LC 215.Kth Largest Element in an Array
- LC 378.Kth Smallest Element in a Sorted Matrix
- LC 692.Top K Frequent Words
Dynamic Programming⌗
Choose items with presum⌗
class Solution {
private List<List<Integer>> piles;
private int[][] memo;
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
this.piles = piles;
this.memo = new int[piles.size()][k + 1];
for (int i = 0; i < piles.size(); i++) {
Arrays.fill(memo[i], -1);
}
return dp(piles.size() - 1, k);
}
private int dp(int i, int k) {
if (k == 0) return 0;
if (i < 0) return Integer.MIN_VALUE >> 1;
if (memo[i][k] != -1) return memo[i][k];
List<Integer> pile = piles.get(i);
int n = pile.size();
// int[] presum = new int[n + 1];
// for (int j = 1; j <= n; j++) {
// presum[j] = presum[j - 1] + pile.get(j - 1);
// }
int ans = Integer.MIN_VALUE >> 1;
int v = 0;
for (int j = 0; j <= Math.min(n, k); j++) {
// int v = presum[j];
ans = Math.max(ans, dp(i - 1, k - j) + v);
if (j < n) v += pile.get(j);
}
return memo[i][k] = ans;
}
}
Exercises:
LC 2209.Minimum White Tiles After Covering With Carpets LC 2218.Maximum Value of K Coins From Piles LC 410.Split Array Largest Sum
Split intervel⌗
class Solution {
private int n;
private int[][] max;
private int[][] memo;
public int minDifficulty(int[] jobDifficulty, int d) {
this.n = jobDifficulty.length;
this.max = new int[n][n];
this.memo = new int[n][d];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
for (int i = 0; i < n; i++) {
for (int j = i, m = jobDifficulty[j]; j < n; j++) {
m = Math.max(m, jobDifficulty[j]);
max[i][j] = m;
}
}
int ret = f(0, d - 1);
return ret == Integer.MAX_VALUE >> 1 ? -1 : ret;
}
private int f(int i, int p) {
if (i >= n) return Integer.MAX_VALUE >> 1;
if (p == 0) return max[i][n - 1];
if (memo[i][p] != -1) return memo[i][p];
int ret = Integer.MAX_VALUE >> 1;
for (int j = i; j < n; j++) {
ret = Math.min(ret, max[i][j] + f(j + 1, p - 1));
}
return memo[i][p] = ret;
}
}
Exercises:
knapsack⌗
0-1 knapsack⌗
// dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i])
int knapsack(int[] W, int[] V, int n, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = capacity; j >= W[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - W[i]] + V[i]);
}
}
return dp[capacity];
}
Exercises:
Bounded knapsack⌗
// dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - W[i] * k] + V[i] * k)
int knapsack(int[] W, int[] V, int[] S, int n, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = capacity; j >= W[i]; j--) {
for (int k = 1; k <= S[i]; k++) {
if (W[i] * k > j) break;
dp[j] = Math.max(dp[j], dp[j - W[i] * k] + V[i] * k);
}
}
}
return dp[capacity];
}
Exercises:
Unbounded knapsack⌗
int knapsack(int[] W, int[] V, int n, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = W[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j - W[i]] + V[i]);
}
}
return dp[capacity];
}
Exercises:
String⌗
LCS (Longest Common Subsequence)⌗
int LCS(String s, String t) {
int n = s.length(), m = t.length();
// dp[i][j] := the longest common subsequence length of s[0:i] and t[0:j]
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
Exercises:
- LC 1143.Longest Common Subsequence
- LC 516.Longest Palindromic Subsequence
- LC 392.Is Subsequence
- LC 583.Delete Operation for Two Strings
Edit Distance⌗
int minDistance(String s, String t) {
int n = s.length(), m = t.length();
int[][] dp = new int[n + 1][m + 1];
// s is empty
for (int j = 0; j <= m; j++) {
dp[0][j] = j;
}
// t is empty
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
//
// s [xxxxx] A
//
// t [xxxxx] B
//
dp[i][j] = Math.min(dp[i - 1][j] + 1, // delete(A)
Math.min(dp[i][j - 1] + 1, // insert(B)
dp[i - 1][j - 1] + 1)); // replace(A, B)
}
}
}
return dp[n][m];
}
Exercises:
LIS (Longest Increasing Subsequence)⌗
class Solution {
public int lengthOfLIS(int[] nums) {
List<Integer> list = new ArrayList<>();
for (var num : nums) {
int m = lowerBound(list, num);
if (m == list.size()) {
list.add(num);
} else {
list.set(m, num);
}
}
return list.size();
}
private int lowerBound(List<Integer> list, int x) {
int l = 0, r = list.size();
while (l < r) {
int m = l + (r - l) / 2;
if (list.get(m) < x) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
}
Exercises:
- LC 300.Longest Increasing Subsequence
- LC 1964.Find the Longest Valid Obstacle Course at Each Position
- LC 1671.Minimum Number of Removals to Make Mountain Array
- LC 334.Increasing Triplet Subsequence
- LC 665.Non-decreasing Array
Palindrom⌗
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
// dp[i][j] := s[i:j] == true that means in the range [i:j] is a palindrome
boolean[][] dp = new boolean[n][n];
int start = 0, maxLen = 0;
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
//
// dp[i][j] = true if len(s[i:j]) <= 2 or dp[i + 1][j - 1] is palindrome
//
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = len <= 2 || dp[i + 1][j - 1];
}
// Update the answer
if (dp[i][j] && len > maxLen) {
start = i;
maxLen = len;
}
}
}
return s.substring(start, start + maxLen);
}
}
Exercises:
- LC 5.Longest Palindromic Substring
- LC 647.Palindromic Substrings
- LC 2472.Maximum Number of Non-overlapping Palindrome Substrings
Interval DP⌗
class Solution {
private String s;
private int minLength;
private long[][] memo;
private int mod = (int) 1e9 + 7;
public int beautifulPartitions(String s, int k, int minLength) {
this.s = s;
this.minLength = minLength;
this.memo = new long[s.length()][k + 1];
for (int i = 0; i < s.length(); i++) {
Arrays.fill(memo[i], -1);
}
return (int) dp(0, k);
}
private long dp(int i, int k) {
if (i == s.length() && k == 0) return 1;
if (i >= s.length() || k < 0) return 0;
if (memo[i][k] != -1) return memo[i][k];
// xxxxxxxxxx
// i j
// j - i + 1 >= minLength
// j >= minLength + i - 1
long ret = 0;
if (isPrime(s.charAt(i))) {
for (int j = minLength + i - 1; j < s.length(); j++) {
if (s.length() - (j + 1) + 1 < (k - 1) * minLength) break;
if (isPrime(s.charAt(j))) continue;
ret += dp(j + 1, k - 1);
ret %= mod;
}
}
return memo[i][k] = ret;
}
private boolean isPrime(char c) {
return c == '2' || c == '3' || c == '5' || c == '7';
}
}
Exercises:
2D Grid Path⌗
class Solution {
private int m, n;
private int[][] grid;
private Integer[][][] memo;
private int[][] moves = {
// x1 y1 x2
{1, 0, 1, 0},
{1, 0, 0, 1},
{0, 1, 1, 0},
{0, 1, 0, 1}
// y2(useless)
};
public int cherryPickup(int[][] grid) {
this.m = grid.length;
this.n = grid[0].length;
this.grid = grid;
this.memo = new Integer[n][m][n];
// robot 1: (0, 0)
// robot 2: (0, 0)
// ^
// don't need
//
//
// x1 + y1 = x2 + y2
// y2 = x1 + y1 - x2
return Math.max(0, dp(0, 0, 0));
}
private int dp(int x1, int y1, int x2) {
int y2 = x1 + y1 - x2;
if (x1 >= m || x2 >= m ||
y1 >= n || y2 >= n) return Integer.MIN_VALUE >> 1;
if (grid[y1][x1] == -1 ||
grid[y2][x2] == -1) return Integer.MIN_VALUE >> 1;
if (x1 == n - 1 && y1 == m - 1) return grid[y1][x1];
if (memo[x1][y1][x2] != null) return memo[x1][y1][x2];
int res = Integer.MIN_VALUE >> 1;
for (var move : moves) {
res = Math.max(res, dp(x1 + move[0], y1 + move[1], x2 + move[2]));
}
res += grid[y1][x1];
if (y1 != y2 && x1 != x2) res += grid[y2][x2];
return memo[x1][y1][x2] = res;
}
}
Exercises:
Sparse Table⌗
class SparseTable {
private int[] log2;
//
// dp[p][i] := minimum number in arr[i: i + 2**p - 1]
//
private int[][] dp;
public SparseTable(int[] arr) {
computeLog2(arr.length);
int n = arr.length;
this.dp = new int[log2[n] + 1][n];
for (int i = 0; i < n; i++) {
dp[0][i] = arr[i];
}
for (int p = 1; p < dp.length; p++) {
for (int i = 0; i + (1 << p - 1) < n; i++) {
dp[p][i] = Math.max(dp[p - 1][i], dp[p - 1][i + (1 << p - 1)]);
}
}
}
private void computeLog2(int n) {
this.log2 = new int[n + 1];
for (int i = 2; i <= n; i++) {
log2[i] = log2[i / 2] + 1;
}
}
public int query(int l, int r) {
int p = log2[r - l + 1];
return Math.max(dp[p][l], dp[p][r - (1 << p) + 1]);
}
}
It can be used for (min, max, gcd) range query, below is the MinSparseTable implementation.
Exercises:
Graph⌗
Shortest Path⌗
Dijkstra⌗
// vertex are 0-indexed
//
// n: number of vertexes
// s: the start vertex
// edge: [u, v, w]
int[] dijkstra(int n, int s, int[][] edges) {
// build graph
List<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
graph[u].add(new int[]{v, w});
}
// init
// {node, distance}
Queue<int[]> queue = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
int[] dist = new int[n];
int[] prev = new int[n];
for (int i = 0; i < n; i++) {
dist[i] = Integer.MAX_VALUE >> 1;
prev[i] = -1;
}
dist[s] = 0;
queue.offer(new int[] {s, 0});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int u = curr[0], d = curr[1];
if (dist[u] != d) continue;
for (int[] next : graph[u]) {
int v = next[0], w = next[1];
if (d + w < dist[v]) {
dist[v] = d + w;
prev[v] = u;
queue.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
Exercises:
- LC 45.Jump Game II
- LC 743.Network Delay Time
- LC 1368.Minimum Cost to Make at Least One Valid Path in a Grid
- LC 1879.Minimum XOR Sum of Two Arrays
- LC 2203.Minimum Weighted Subgraph With the Required Paths
- LC 1514.Path with Maximum Probability
- LC 1976.Number of Ways to Arrive at Destination
- LC 1786.Number of Restricted Paths From First to Last Node
- LC 1631.Path With Minimum Effort
- LC 2290.Minimum Obstacle Removal to Reach Corner
- LC 2492.Minimum Score of a Path Between Two Cities
Bellman-Ford⌗
int[] bellmanFord(int n, int s, int[][] edges) {
int[] dist = new int[n];
int[] prev = new int[n];
for (int i = 0; i < n; i++) {
dist[i] = Integer.MAX_VALUE >> 1;
prev[i] = -1;
}
dist[s] = 0;
for (int i = 0; i < n - 1; i++) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
// dist[v] = Math.min(dist[v], dist[u] + w);
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
}
}
}
// check for negative-weight cycles
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
// dist[v] = Math.min(dist[v], dist[u] + w);
if (dist[u] + w < dist[v]) {
System.out.println("Graph contains a negative-weight cycle.");
}
}
return dist;
}
Exercises:
Floyd-Warshall⌗
class Solution {
// Floyd
public int networkDelayTime(int[][] times, int n, int k) {
int[][] dp = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) dp[i][j] = 0;
else dp[i][j] = Integer.MAX_VALUE >> 1;
}
}
for (var time : times) {
int u = time[0], v = time[1], w = time[2];
dp[u][v] = w;
}
for (int l = 1; l <= n; l++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i][l] + dp[l][j]);
}
}
}
int maxTime = 0;
for (int j = 1; j <= n; j++) {
maxTime = Math.max(maxTime, dp[k][j]);
}
if (maxTime == Integer.MAX_VALUE >> 1) return -1;
return maxTime;
}
}
Toplogical sort⌗
void toplogicalSort(int n, int[][] edges) {
// build graph
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
int[] inDegree = new int[n];
for (var edge : edges) {
int u = edge[0], v = edge[1];
// u -> v
graph[u].add(v);
inDegree[v]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
// leaf node don't have pre requirements, add it to the queue
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int u = queue.poll();
for (var v : graph[u]) {
inDegree[v]--;
// if node v don't have pre requirements anymore, add it to the queue
if (inDegree[v] == 0) {
queue.offer(v);
}
}
}
}
}
Exercises:
- LC 207.Course Schedule
- lC 210.Course Schedule II
- LC 310.Minimum Height Trees
- LC 2115.Find All Possible Recipes from Given Supplies
- LC 1857.Largest Color Value in a Directed Graph
- LC 1591.Strange Printer II
- LC 2127.Maximum Employees to Be Invited to a Meeting
- LC 2192.All Ancestors of a Node in a Directed Acyclic Graph
- LC 2477.Minimum Fuel Cost to Report to the Capital
Union Find⌗
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
this.parent = new int[n];
this.rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
/* rank[i] = 0; */
}
}
public boolean union(int u, int v) {
int pu = find(u);
int pv = find(v);
if (pu == pv) return false;
if (rank[pu] < rank[pv]) {
parent[pu] = pv;
} else {
parent[pv] = pu;
}
if (rank[pu] == rank[pv]) {
rank[pu]++;
}
return true;
}
public int find(int u) {
if (parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
}
Exercises:
- LC 547.Number of Provinces
- LC 1584.Min Cost to Connect All Points
- LC 684.Redundant Connection
- LC 1971.Find if Path Exists in Graph
- LC 959.Regions Cut By Slashes
- LQ 110.合根植物
- LC 947.Most Stones Removed with Same Row or Column
- LC 130.Surrounded Regions
- LC 952.Largest Component Size by Common Factor
- LQ 185.修改数组
- LC 2092.Find All People With Secret
- LQ 1505.剪邮票
- LC 2076.Process Restricted Friend Requests
- LC 1722.Minimize Hamming Distance After Swap Operations
- LC 2157.Groups of Strings
- LC 1202.Smallest String With Swaps
- LC 990.Satisfiability of Equality Equations
- LC 2493.Divide Nodes Into the Maximum Number of Groups
- LC 2492.Minimum Score of a Path Between Two Cities
- LC 1061.Lexicographically Smallest Equivalent String
Tree⌗
Segment tree⌗
1
2
class SegmentTree {
class Node {
int val, l, r;
Node left, right;
Node(int l, int r) {
this(0, l, r);
}
Node(int val, int l, int r) {
this.val = val;
this.l = l;
this.r = r;
}
}
private static final int INVALID_VALUE = 0;
private Node root;
public SegmentTree(int[] nums) {
root = build(nums, 0, nums.length - 1);
}
private Node build(int[] nums, int l, int r) {
if (l == r) {
return new Node(nums[l], l, r);
}
int m = (l + r) / 2;
Node root = new Node(l, r);
root.left = build(nums, l, m);
root.right = build(nums, m + 1, r);
root.val = combine(root.left.val, root.right.val);
return root;
}
public void update(int index, int val) {
update(root, index, val);
}
private void update(Node root, int index, int val) {
if (root.l == index && root.r == index) {
root.val = val;
return;
}
int m = (root.l + root.r) / 2;
if (index <= m) {
update(root.left, index, val);
} else {
update(root.right, index, val);
}
root.val = combine(root.left.val, root.right.val);
}
public int query(int left, int right) {
return query(root, left, right);
}
private int query(Node root, int l, int r) {
if (l > r) return INVALID_VALUE;
if (root.l == l && root.r == r) {
return root.val;
}
int m = (root.l + root.r) / 2;
return combine(query(root.left, l, Math.min(m, r)),
query(root.right, Math.max(m + 1, l), r));
}
private int combine(int left, int right) {
return left + right;
}
}class SegmentTree {
private int[] tree;
private int[] leaf;
private int n;
private CombineStrategy strategy;
public SegmentTree(int[] arr) {
this(arr, new SumCombineStrategy());
}
public SegmentTree(int[] arr, CombineStrategy strategy) {
this.n = arr.length;
this.leaf = arr;
this.tree = new int[(n << 2) + 1];
this.strategy = strategy;
build(0, 0, n - 1);
}
private void build(int root, int l, int r) {
if (l == r) {
tree[root] = leaf[l];
return;
}
int m = (l + r) >> 1;
int left = left(root), right = right(root);
build(left, l, m);
build(right, m + 1, r);
tree[root] = strategy.combine(tree[left], tree[right]);
}
public int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
private int query(int root, int l, int r, int L, int R) {
if (L > R) return strategy.invalidValue();
if (l == L && r == R) {
return tree[root];
}
int m = (l + r) >> 1;
int left = left(root), right = right(root);
return strategy.combine(query(left, l, m, L, Math.min(m, R)),
query(right, m + 1, r, Math.max(m + 1, L), R));
}
public void update(int i, int val) {
update(0, 0, n - 1, i, val);
}
private void update(int root, int l, int r, int i, int val) {
if (l == i && r == i) {
leaf[i] = val;
tree[root] = val;
return;
}
int m = (l + r) >> 1;
int left = left(root), right = right(root);
if (i <= m) {
update(left, l, m, i, val);
} else {
update(right, m + 1, r, i, val);
}
tree[root] = strategy.combine(tree[left], tree[right]);
}
private int left(int root) {
return (root << 1) + 1;
}
private int right(int root) {
return (root << 1) + 2;
}
public static class MaxCombineStrategy implements CombineStrategy {
@Override
public int invalidValue() {
return Integer.MIN_VALUE;
}
@Override
public int combine(int a, int b) {
return Math.max(a, b);
}
}
public static class SumCombineStrategy implements CombineStrategy {
@Override
public int invalidValue() {
return 0;
}
@Override
public int combine(int a, int b) {
return a + b;
}
}
public interface CombineStrategy {
int invalidValue();
int combine(int a, int b);
}
}Exercises:
- LC 307.Range Sum Query - Mutable
- LC 1578.Minimum Time to Make Rope Colorful
- LC 2462.Total Cost to Hire K Workers
Fenwick tree⌗
class FenwickTree {
// 1-indexed
private int[] tree;
public FenwickTree(int[] nums) {
int n = nums.length;
this.tree = new int[n + 1];
// deep copy nums[0:] to tree[1:]
System.arraycopy(nums, 0, tree, 1, n);
for (int i = 1; i <= n; i++) {
int j = i + lsb(i);
if (j <= n) tree[j] += tree[i];
}
}
//
// 1-indexed
//
// delta = newVal - oldVal
//
public void update(int i, int delta) {
while (i < tree.length) {
tree[i] += delta;
i += lsb(i);
}
}
//
// 1-indexed
//
// sumOfRange(l, r) == presum(r) - presum(l - 1)
//
public int presum(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lsb(i);
}
return sum;
}
//
// lsb stands for least significant bit
//
// x: 10111101000
//
// -x: (Negative numbers are stored in the form of Twos' complement in the computer)
// 01000010111 (Ones' complement)
// 01000011000 (Twos' complement)
//
//
// 10111101000
// & 01000011000
// -------------
// 00000001000
//
private int lsb(int i) {
return i & -i;
}
}
Exercises:
- LC 307.Range Sum Query - Mutable
- LC 1409.Queries on a Permutation With Key
- LC 1395.Count Number of Teams
- LC 1375.Number of Times Binary String Is Prefix-Aligned
- LC 2179.Count Good Triplets in an Array
Prefix Tree (Trie)⌗
class Trie {
class Node {
boolean isWord;
Node[] children = new Node[26];
}
Node root;
public Trie() {
root = new Node();
}
public void insert(String word) {
Node node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new Node();
}
node = node.children[index];
}
node.isWord = true;
}
public boolean search(String word) {
Node node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isWord; // !!!!
}
public boolean startsWith(String prefix) {
Node node = root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true; // !!!!
}
}
Exercises:
- LC 208.Implement Trie (Prefix Tree)
- LC 1032.Stream of Characters
- LC 421.Maximum XOR of Two Numbers in an Array
- LC 211.Design Add and Search Words Data Structure
- LC 745.Prefix and Suffix Search
- LC 1268.Search Suggestions System
- LC 820.Short Encoding of Words
- LC 336.Palindrome Pairs
- LC 2416.Sum of Prefix Scores of Strings
- LC 212.Word Search II
DFS⌗
Backtracking⌗
Combination⌗
class Combination {
public List<List<Integer>> C(int[] nums, int k) {
List<List<Integer>> res = new ArrayList<>();
C(nums, k, 0, new ArrayList<>(), res);
return res;
}
private void C(int[] nums, int k, int s, List<Integer> temp, List<List<Integer>> res) {
if (temp.size() == k) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = s; i < nums.length; i++) {
// this line use to remove duplicates,
// but `nums` needs to be sorted first
// if (i > s && nums[i] == nums[i - 1]) continue;
temp.add(nums[i]);
C(nums, k, i + 1, temp, res);
temp.remove(temp.size() - 1);
}
}
}
Exercises:
- LC 77.Combinations
- LC 39.Combination Sum
- LC 40.Combination Sum II
- LC 216.Combination Sum III
- LC 17.Letter Combinations of a Phone Number
- LC 2305.Fair Distribution of Cookies
Permutation⌗
class Permutation {
public List<List<Integer>> P(int[] nums, int k) {
List<List<Integer>> res = new ArrayList<>();
P(nums, k, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
private void P(int[] nums, int k, boolean[] used, List<Integer> temp, List<List<Integer>> res) {
if (temp.size() == k) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
// this line use to remove duplicates,
// but `nums` needs to be sorted first
// if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
temp.add(nums[i]);
used[i] = true;
P(nums, k, used, temp, res);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
}
Exercises:
Binary Exponentiation⌗
Basic⌗
long pow(int a, int n) {
// a %= MOD;
long res = 1;
while (n > 0) {
if ((n & 1) == 1) {
// res = res * a % MOD;
res *= a;
}
// a = a * a % MOD;
a *= a;
n >>= 1;
}
return res;
}
Exercises:
Matrix⌗
class MatrixFastPow {
public int[][] pow(int[][] A, int n) {
int[][] res = new int[A.length][A[0].length];
// identity matrix
for (int i = 0; i < A.length; i++) {
res[i][i] = 1;
}
while (n > 0) {
if ((n & 1) == 1) {
// res *= A;
res = dot(res, A);
}
// A *= A;
A = dot(A, A);
n >>= 1;
}
return res;
}
private int[][] dot(int[][] A, int[][] B) {
int[][] C = new int[A.length][B[0].length];
for (int i = 0; i < C.length; i++) {
for (int j = 0; j < C[0].length; j++) {
for (int k = 0; k < B.length; k++) {
// modular if needed
// C[i][j] += A[i][k] % MOD * B[k][j] % MOD;
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
}
Exercises:
Stack⌗
Monotonic Stack⌗
void monotonicStack(int[] nums) {
Stack<Integer> stack = new Stack<>();
for (int num : nums) {
// We want to keep a monotonously increasing sequence, so when `num` is
// less than the top element of the stack, that means the balance is
// broken, and we need pop the top element in order to fix the its
// monotonicity.
//
// HINT: If you want to keep a monotonously decreasing sequence, just
// change `num < stack.peek()` to `num > stack.peek()`
while (!stack.isEmpty() && num < stack.peek()) {
stack.pop();
}
// As we can go here, means that `num` is greater or equal than
// `stack.peek()`, just push it into the stack.
stack.push(num);
}
}
Exercises:
- LC 316.Remove Duplicate Letters
- LC 402.Remove K Digits
- LC 496.Next Greater Element I
- LC 496.Next Greater Element II
- LC 739.Daily Temperatures
- LC 1673.Find the Most Competitive Subsequence
- LC 2030.Smallest K-Length Subsequence With Occurrences of a Letter
- LC 84.Largest Rectangle in Histogram
- LC 85.Maximal Rectangle
- LC 1475.Final Prices With a Special Discount in a Shop
- LC 907.Sum of Subarray Minimums
- LC 2104.Sum of Subarray Ranges
- LC 1856.Maximum Subarray Min-Product
- LC 849.Maximize Distance to Closest Person
- LC 901.Online Stock Span
- LC 2472.Maximum Number of Non-overlapping Palindrome Substrings
Binary Search⌗
Find a exact value⌗
Single target⌗
// [l, r]
int bSearch(int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (f(m) < x) {
l = m + 1;
} else if (f(m) > x){
r = m - 1;
} else {
return m;
}
}
return -1;
}
Range target⌗
// [l, r]
boolean rangeQuery(int l, int r, int lower, int upper) {
while (l <= r) {
int m = l + (r - l) / 2;
if (f(m) < lower) {
l = m + 1;
} else if (f(m) > upper) {
r = m - 1;
} else {
return true;
}
}
return false;
}
This is use to check there is a value between lower and upper.
Exercises:
Approach a value⌗
Lower Bound⌗
//
// [l, r)
//
// l r
// A: 1 2 3 4 5 5 5 5 5 6 7
// x: 5
//
// r
// l
// A: 1 2 3 4 5 5 5 5 5 6 7
// x: 5
//
int lowerBound(int l, int r, int x) {
while (l < r) {
int m = l + (r - l) / 2;
if (f(m) < x) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
Exercises:
- LC 2080.Range Frequency Queries
- LC 35.Search Insert Position
- LC 540.Single Element in a Sorted Array
- LC 878.Nth Magical Number
- LC 1201.Ugly Number III
- LC 875.Koko Eating Bananas
- LC 2141.Maximum Running Time of N Computers
- LC 2226.Maximum Candies Allocated to K Children
- LC 2300.Successful Pairs of Spells and Potions
- LC 374.Guess Number Higher or Lower
- LC 2476.Closest Nodes Queries in a Binary Search Tree
- LC 1011.Capacity To Ship Packages Within D Days
Upper Bound⌗
//
// [l, r)
//
// l r
// A: 1 2 3 4 5 5 5 5 5 6 7
// x: 5
//
// r
// l
// A: 1 2 3 4 5 5 5 5 5 6 7
// x: 5
//
int upperBound(int l, int r, int x) {
while (l < r) {
int m = l + (r - l) / 2;
if (f(m) <= x) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
Exercises:
Ternary Search⌗
class Solution {
private int[] nums, cost;
public long minCost(int[] nums, int[] cost) {
int n = nums.length;
this.nums = nums;
this.cost = cost;
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
// l m1 m2 r
int l = min, r = max;
while (r - l > 3) {
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
if (cost(m2) < cost(m1)) {
l = m1;
} else {
r = m2;
}
}
long ret = Long.MAX_VALUE;
for (int m = l; m <= r; m++) {
ret = Math.min(ret, cost(m));
}
return ret;
}
private long cost(int m) {
long ret = 0;
for (int i = 0; i < nums.length; i++) {
ret += (long) Math.abs(nums[i] - m) * cost[i];
}
return ret;
}
}
Exercises:
Bit Manipulation⌗
Least significant bits⌗
//
// x: 10111101000
//
// -x: (Negative numbers are stored in the form of Twos' complement in the computer)
// 01000010111 (Ones' complement)
// 01000011000 (Twos' complement)
//
//
// 10111101000
// & 01000011000
// -------------
// 00000001000
//
int lsb(x) {
return x & -x;
}
Submask Enumeration⌗
for (int subset = bitmask; subset > 0; subset = (subset - 1) & bitmask) {
// do what you want with the current subset...
}
I took this template and explination from here.
Why does this work? The subsets must be included in range [0, bitmask], and if
we iterate from bitmask to 0 one by one, we are guaranteed to visit the bitmask
of every subset along the way.
But we can also meet those that are not a subset of bitmask. Fortunately,
instead of decrementing subset by one at each iteration, we can use subset = (subset - 1) & bitmask to ensure that each subset only contains characters that
exist in bitmask.
Also, we will not miss any subset because subset - 1 turns at most one 1 into
0.
Exercises:
Gosper’s Hack⌗
int limit = 1 << n;
for (int k = n; k >= 1; k--) {
int state = (1 << k) - 1;
while (state < limit) {
// do what you want with the current state...
int c = state & -state;
int r = state + c;
state = (((r ^ state) >> 2) / c) | r;
}
}
Sliding Window⌗
Window without repeat⌗
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] next = new int[128];
Arrays.fill(next, -1);
int ans = 0;
for (int i = 0, j = 0; j < s.length(); j++) {
int index = s.charAt(j);
i = Math.max(i, next[index] + 1);
//
// window [i, j] has no repeating elements
//
ans = Math.max(ans, j - i + 1);
next[index] = j;
}
return ans;
}
}
Exercises:
- LC 3.Longest Substring Without Repeating Characters
- LC 1876.Substrings of Size Three with Distinct Characters
- LC 1695.Maximum Erasure Value
- LC 2405.Optimal Partition of String
- LC 2461.Maximum Sum of Distinct Subarrays With Length K
Window size have relation with its sum⌗
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int ans = 0;
int save = 0;
for (int i = 0, j = 0; j < nums.length; j++) {
save += nums[j];
// make sure the window is valid
if (j - i + 1 > save) {
i = j + 1;
save = 0;
}
// update
ans = Math.max(ans, j - i + 1);
// other things
}
return ans;
}
}
Exercises:
- LC 485.Max Consecutive Ones
- LC 1004.Max Consecutive Ones III
- LC 1343.Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
- LC 2134.Minimum Swaps to Group All 1’s Together II
- LC 1658.Minimum Operations to Reduce X to Zero
- LC 2302.Count Subarrays With Score Less Than K
Diff Array & Sweep Line⌗
1D⌗
// updates[i] = [x1, x2, delta]
//
// x1 x2
// +------+
//
void f(int[][] updates) {
int[] diff = new int[N];
for (var update : updates) {
int x1 = update[0], x2 = update[1];
int delta = update[2];
diff[x1 ] += delta;
diff[x2 + 1] -= delta;
}
// convert diff to presum
for (int i = 0; i < N - 1; i++) {
diff[i + 1] += diff[i];
}
}
Exercises:
- LC 1109.Corporate Flight Bookings
- LC 732.My Calendar III
- LC 56.Merge Intervals
- LQ 1276.小明的彩灯
- LC 1094.Car Pooling
- LC 2251.Number of Flowers in Full Bloom
- LC 2381.Shifting Letters II
- LC 2406.Divide Intervals Into Minimum Number of Groups
2D⌗
// updates[i] = [x1, y1, x2, y2, delta]
//
// (x1, y1)
// +------+
// | |
// | |
// +------+
// (x2, y2)
//
void f(int[][] updates) {
int[][] diff = new int[N][N];
for (var update : updates) {
int x1 = update[0], y1 = update[1];
int x2 = update[2], y2 = update[3];
int delta = update[4];
diff[x1 ][y1 ] += delta;
diff[x1 ][y2 + 1] -= delta;
diff[x2 + 1][y1 ] -= delta;
diff[x2 + 1][y2 + 1] += delta;
}
// convert diff to presum
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N; j++) {
diff[i + 1][j] += diff[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1; j++) {
diff[i][j + 1] += diff[i][j];
}
}
}
Exercises:
- LC 2132.Stamping the Grid
- LC 850.Rectangle Area II
- LC 2250.Count Number of Rectangles Containing Each Point
3D⌗
// updates[i] = [x1, y1, z1, x2, y2, z2, delta]
void f(int[][] updates) {
int[][][] diff = new int[N][N][N];
for (var update : updates) {
int x1 = update[0], y1 = update[1], z1 = update[2];
int x2 = update[3], y2 = update[4], z2 = update[5];
int delta = update[6];
diff[x1 ][y1 ][z1 ] += delta; // 000
diff[x1 ][y1 ][z2 + 1] -= delta; // 001
diff[x1 ][y2 + 1][z1 ] -= delta; // 010
diff[x1 ][y2 + 1][z2 + 1] += delta; // 011
diff[x2 + 1][y1 ][z1 ] -= delta; // 100
diff[x2 + 1][y1 ][z2 + 1] += delta; // 101
diff[x2 + 1][y2 + 1][z1 ] += delta; // 110
diff[x2 + 1][y2 + 1][z2 + 1] -= delta; // 111
// Apply `+` when there is even bit ones
// otherwise apply `-`
}
// convert diff to presum
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
diff[i + 1][j][k] += diff[i][j][k];
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1; j++) {
for (int k = 0; k < N; k++) {
diff[i][j + 1][k] += diff[i][j][k];
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N - 1; k++) {
diff[i][j][k + 1] += diff[i][j][k];
}
}
}
}
Exercises:
Check From The Middle⌗
Count smaller/greater before/after self (Merge sort or FenwickTree)⌗
MergeSort
FenwickTree
int[] nums;
int[] temp;
int[] smallerAfterSelf;
// l: inclusive
// r: exclusive
void sort(int[] sorted, int l, int r) {
if (l >= r - 1) return;
int m = l + (r - l) / 2;
sort(sorted, l, m);
sort(sorted, m, r);
for (int i = l; i < m; i++) {
smallerAfterSelf[i] += lowerBound(sorted, m, r, nums[i]) - m;
}
// merge
int i = l, j = m, k = 0;
while (i < m && j < r) {
if (sorted[i] < sorted[j]) {
temp[k++] = sorted[i++];
} else {
temp[k++] = sorted[j++];
}
}
while (i < m) temp[k++] = sorted[i++];
while (j < r) temp[k++] = sorted[j++];
for (i = l, j = 0; i < r; i++, j++) {
sorted[i] = temp[j];
}
}void f(int[] nums) {
int[] map = new int[n];
for (int i = 0; i < n; i++) {
map[nums[i]] = i;
}
int[] prevSmaller = new int[n];
FenwickTree bit = new FenwickTree(n);
for (int i = 0; i < n; i++) {
int a = map[nums[i]];
bit.update(a, 1);
prevSmaller[i] = bit.sumOfRange(0, a - 1);
}
}Exercises:
- LC 315.Count of Smaller Numbers After Self
- LC 2179.Count Good Triplets in an Array
- LC 493.Reverse Pairs
- LC 2563.Count the Number of Fair Pairs
Find the first index that smaller/greater before/after self (Monotonic stack)⌗
Min/Max sum of n-th elements before/after self (PriorityQueue)⌗
void f(int[] nums, int n) {
Queue<Integer> leftQueue = new PriorityQueue<>(Collections.reverseOrder());
long[] leftMin = new long[nums.length];
long sum = 0;
for (int i = 0; i < n << 1; i++) {
leftQueue.offer(nums[i]);
sum += nums[i];
if (leftQueue.size() > n) {
sum -= leftQueue.poll();
}
leftMin[i] = sum;
}
}
Exercises:
Parentheses⌗
1
2
class Solution {
public int minAddToMakeValid(String s) {
int stack = 0;
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack++; // push '('
} else {
if (stack > 0) {
stack--; // pop '('
} else {
cnt++; // need insert a '(' to make s valid
}
}
}
//
// if stack = 3, means we need to insert 3 ')' to make s valid
//
// v
return cnt + stack;
}
}class Solution {
public boolean checkValidString(String s) {
int min = 0, max = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
min++;
max++;
} else if (c == ')') {
min--;
max--;
} else /* if (c == '*') */ {
min--; // treat * as )
max++; // treat * as (
}
if (max < 0) break;
if (min < 0) min = 0; // * allow empty
}
return min == 0;
}
}Exercises:
- LC 20.Valid Parentheses
- LC 32.Longest Valid Parentheses
- LC 856.Score of Parentheses
- LC 921.Minimum Add to Make Parentheses Valid
- LC 946.Validate Stack Sequences
- LC 1249.Minimum Remove to Make Valid Parentheses
- LC 1541.Minimum Insertions to Balance a Parentheses String
- LC 1963.Minimum Number of Swaps to Make the String Balanced
- LC 678.Valid Parenthesis String
- LC 2116.Check if a Parentheses String Can Be Valid
Array⌗
Counting⌗
class Solution {
public int countSubarrays(int[] nums, int k) {
int n = nums.length;
int m = findK(nums, k);
Map<Integer, Integer> diff = new HashMap<>();
int greater = 0, less = 0;
for (int i = m; i >= 0; i--) {
if (nums[i] > k) {
greater++;
} else if (nums[i] < k) {
less++;
}
int d = greater - less;
diff.put(d, diff.getOrDefault(d, 0) + 1);
}
int ret = 0;
greater = less = 0;
for (int i = m; i < n; i++) {
if (nums[i] > k) {
greater++;
} else if (nums[i] < k) {
less++;
}
int d = greater - less;
ret += diff.getOrDefault(-d, 0) + diff.getOrDefault(1 - d, 0);
}
return ret;
}
private int findK(int[] A, int k) {
for (int i = 0; i < A.length; i++) {
if (A[i] == k) {
return i;
}
}
return -1;
}
}
Exercises:
Math⌗
Linear Algebra⌗
Gaussian Elimination⌗
class Solution {
public void solve(double[][] A, double[] b) {
int n = A.length;
System.out.println("Argumented Matrix: ");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(A[i][j] + "\t");
}
System.out.println("|\t" + b[i]);
}
// Elimination
for (int i = 0; i < n; i++) {
// Find pivot row
int max = i;
for (int j = i + 1; j < n; j++) {
if (Math.abs(A[j][i]) > Math.abs(A[max][i])) {
max = j;
}
}
// Swap
double[] temp = A[i]; A[i] = A[max]; A[max] = temp;
double t = b[i]; b[i] = b[max]; b[max] = t;
if (Math.abs(A[i][i]) <= 1e-5) {
throw new ArithmeticException("Matrix is singular or nearly singular");
}
for (int j = i + 1; j < n; j++) {
double factor = A[j][i] / A[i][i];
for (int k = i; k < n; k++) {
A[j][k] -= factor * A[i][k];
}
b[j] -= factor * b[i];
}
}
// Back-substitution
double[] x = new double[n];
for (int i = n - 1; i >= 0; i--) {
double sum = 0;
for (int j = i + 1; j < n; j++) {
sum += A[i][j] * x[j];
}
x[i] = (b[i] - sum) / A[i][i];
}
System.out.println();
System.out.println("Solution: ");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
System.out.print("1\t");
} else {
System.out.print("0\t");
}
}
System.out.println("|\t" + x[i]);
}
}
}
GCD & LCM⌗
class Solution {
public int subarrayLCM(int[] nums, int k) {
int n = nums.length;
int ret = 0;
for (int i = 0; i < n; i++) {
int l = 1;
for (int j = i; j < n; j++) {
l = lcm(l, nums[j]);
if (l == k) {
ret++;
}
}
}
return ret;
}
private int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
Exercises:
FastScanner⌗
class FastScanner {
private static final int NULL = '\0';
private static final int BUFFER_CAPACITY = 1 << 18;
private InputStream in;
private byte[] buffer = new byte[BUFFER_CAPACITY];
private int bufferPtr, bufferSize;
public FastScanner(InputStream in) {
this.in = in;
this.bufferPtr = 0;
this.bufferSize = 0;
}
public String next() throws IOException {
byte[] res = new byte[1 << 16];
int len = 0;
byte b = read();
while (b != ' ' && b != '\n' && b != NULL) {
res[len++] = b;
b = read();
}
return new String(res, 0, len);
}
public int nextInt() throws IOException {
int res = 0;
// skip leading non-printable characters
byte b = read();
while (b <= ' ') b = read();
boolean neg = b == '-';
if (neg) b = read();
while (b >= '0' && b <= '9') {
res = res * 10 + b - '0';
b = read();
}
return neg ? res * -1 : res;
}
public long nextLong() throws IOException {
long res = 0;
// skip leading non-printable characters
byte b = read();
while (b <= ' ') b = read();
boolean neg = b == '-';
if (neg) b = read();
while (b >= '0' && b <= '9') {
res = res * 10 + b - '0';
b = read();
}
return neg ? res * -1 : res;
}
public double nextDouble() throws IOException {
double res = 0;
// skip leading non-printable characters
byte b = read();
while (b <= ' ') b = read();
boolean neg = b == '-';
if (neg) b = read();
while (b >= '0' && b <= '9') {
res = res * 10 + b - '0';
b = read();
}
// read decimal part
if (b == '.') {
double w = 10;
b = read();
while (b >= '0' && b <= '9') {
res += (b - '0') / (w);
b = read();
w *= 10;
}
}
return neg ? res * -1 : res;
}
private byte read() throws IOException {
if (bufferPtr >= bufferSize) {
fillBuffer();
}
return buffer[bufferPtr++];
}
private void fillBuffer() throws IOException {
bufferSize = in.read(buffer, 0, BUFFER_CAPACITY);
bufferPtr = 0;
if (bufferSize == -1) {
buffer[0] = NULL;
}
}
}