Provide my code examples to use some useful algorithms
Priority Queue
Java Queue
Binary Search
When mid is equals, sometimes we need to return. Sometimes, we need to move boundary. However, based one business
logic, we may move in the different direction.
For python, it has built function
c = max(0, bisect_right(starts, p) - bisect_left(ends,p))
//part of solution for Leetcode 1011
function shipWithinDays(weights: number[], days: number): number {
let low = Math.max(...weights);
let minC = low;
let high = 0;
for (let w of weights) high = high + w;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (canLoad(weights, days, mid)) {
high = mid - 1;
} else {
low = mid + 1;
}
}
//make sure that small is not below initial low
//also check if small is good enough. Noted that high
//should be smaller than low after done with search
let small = Math.max(high, minC);
if (canLoad(weights, days, small)) return small;
return low;
}
Slid Window
- Start window for index 0
- Move the end index of window one by one
- Create a check to see if current window is good
- Move start window util window is goog again if current window is not good. Sometime, can jump to end index of current slid window directly (Leetcode 1839)
- Think carefully when decide where to move start to
//solution for Leetcode 424. Can solve 1004, 2024 by using this skill
class Solution {
public int characterReplacement(String s, int k) {
//used to store count of char. char value - 'A' is index
var arr = new int[26];
var l = s.length();
int wStart, wEnd, ans, curLength;
wStart=wEnd=ans=curLength=0;
for (wEnd=0; wEnd<l; wEnd++) {
arr[s.charAt(wEnd)-'A']++;
curLength = wEnd -wStart+1;
//see if good. we keep the most occurence of a char
//the difference between the most occurence and length
//is the number of chars to be replaced
if (curLength - this.max(arr) <=k) {
ans = Math.max(ans, curLength);
continue;
}
//if not good. make it good by slid the start of window
//this is core part of slid window
while (curLength - this.max(arr) >k) {
arr[s.charAt(wStart)-'A']--;
wStart++;
curLength = wEnd-wStart+1;
}
}
return ans;
}
//find max value of array
private int max(int[] arr) {
var ans = 0;
for (int n: arr) {
ans = Math.max(ans, n);
}
return ans;
}
}
Bucket Sort
If we are talking about a frequency problem, may think of bucket sort. The main point is to create an list of buckets. Put some elements
into a one bucket. The below we use ascii value of chars as index of an array, so we can put the same chars into the same bucket.
//Leetcode 415
class Solution {
public String frequencySort(String s) {
//create a bucket. use ascii vaues as index.
//all letters are fit into this bucket.
var arr = new int[150];
for (int i=0; i<s.length(); i++) {
var c = s.charAt(i);
arr[c]++;
}
var map = new TreeMap<Integer, Integer>(Collections.reverseOrder());
for (int n: arr) map.put(n, 1);
var b = new StringBuilder();
for (int k : map.keySet()) {
if (k==0) break;
for (int i=0; i<150; i++) {
if (arr[i]==k) {
char c= (char)(i);
for (int j=0; j<k; j++) b.append(c);
}
}
}
return b.toString();
}
}
Linked List
- check is null. list == null
- Create a head. Let a temp = head. Then move temp
- To move. temp.next = new node. temp = new node
- Initiate a empty node. ListNode node = null
//Leet code 2
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = null;
ListNode temp = null;
var n1 = 0;
var n2 = 0;
var sum = 0;
var carry = 0;
var cur = 0;
while (l1!=null || l2!=null) {
n1 = l1!=null ? l1.val : 0;
n2 = l2!=null ? l2.val : 0;
sum = (n1+n2+carry);
carry = sum/10;
cur = sum%10;
var node = new ListNode(cur);
//have not created yet
if (ans==null) {
ans = node;
temp = ans;
} else {
//will move temp
temp.next = node;
temp = node;
}
if (l1 != null) l1=l1.next;
if (l2 != null) l2=l2.next;
}
//after loop all l1 and l2, see if we have carry
if (carry>0) {
temp.next = new ListNode(carry);
}
return ans;
}
}
Stack
Java stack provide function pop(), peek(), push(), empty() and size() etc
//leetcode 921
class Solution {
public int minAddToMakeValid(String s) {
var stack = new Stack<Character>();
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (stack.empty() || c=='(') {
stack.push(c);
continue;
}
if (stack.peek() == '(') {
stack.pop();
} else {
stack.push(c);
}
}
return stack.size();
}
}
Can put object into stack. In some cases, this Java Pair object is very useful
//Leetcode 1209
class Solution {
public String removeDuplicates(String s, int k) {
var stack = new Stack<Pair <Character, Integer>>();
//not need to check if stack is empty
stack.push(new Pair('$', 1));
for (char c: s.toCharArray()) {
if (c != stack.peek().getKey()) {
stack.push(new Pair(c, 1));
} else {
var p = stack.pop();
if (p.getValue()<k-1) {
//push back
stack.push(new Pair(c, (int)p.getValue()+1));
}
}
}
var ans = new StringBuilder();
for (Pair<Character, Integer> p: stack) {
char c = p.getKey();
int count = p.getValue();
if (c=='$') continue;
for (int j=0; j<count; j++) ans.append(c);
}
return ans.toString();
}
}
For Python, we can use list as stack. append() to add the end of list. pop() remove from
the end of list
#leetcode 56
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x:[x[0], x[1]])
ans = []
ans.append(intervals[0])
i=1
l = len(intervals)
while i < l:
cur = intervals[i]
pre = ans.pop()
if pre[1] >= cur[0]:
ans.append([pre[0], max(pre[1], cur[1]) ])
else:
ans.append(pre)
ans.append(cur)
i+=1
return ans
Tree Inorder Traverse
//Leetcode 94
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
var ans = new ArrayList<Integer>();
var stack = new Stack<TreeNode>();
var cur = root;
while (cur!=null || !stack.isEmpty()) {
while(cur!=null) {
stack.add(cur);
//visit left first
cur = cur.left;
}
//read the end of left
cur = stack.pop();
ans.add(cur.val);
//visit right. Although last left does not have right. not last left
//may have right. paht is lowest left, parent node, left node.
cur = cur.right;
}
return ans;
}
}
Here is a example to traverse right, parent and left using the same skill
//Leetcode 1038
class Solution {
public TreeNode bstToGst(TreeNode root) {
//sum so far
int sum = 0;
//in order search. However, right first
var stack = new Stack<TreeNode>();
var cur = root;
while (cur!=null || !stack.isEmpty()) {
while (cur!=null) {
stack.add(cur);
cur = cur.right;
}
cur = stack.pop();
sum = cur.val + sum;
cur.val = sum;
cur = cur.left;
}
return root;
}
}
Tree Preorder traverse
root, left, right..
//leetcode 144
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
var list = new ArrayList<Integer>();
var s = new Stack<TreeNode>();
var cur = root;
while (cur!= null || !s.isEmpty()) {
while (cur!=null) {
//do something here. Inorder traversal, we do something outside while loop!
list.add(cur.val);
s.add(cur);
cur = cur.left;
}
cur= s.pop();
cur = cur.right;
}
return list;
}
}
Build a tree from array list
TreeNode root1 = new TreeNode(list.get(0));
//this node is first connected to root. Then act as moving part
TreeNode temp = root1;
for (int i=1; i<list.size(); i++) {
var node = new TreeNode(list.get(i));
temp.right = node;
temp = node;
}
return root1;
Dynamic Programming
Try to solve a complex problem by solving sub problems.
- Sub problem is easy to solve.
- Solution for sub problem can be used to solve that big problem
- Need to figure out how to merge a sub problems to a big problem. It is also called state transition
- Normally need a one dimension array or a two to remeber the solutions for sub problems.
- Need to fill array or table in some sequence. Therefore, we can do state transition
Here is a solution for Leetcode 516. Longest Palindromic Subsequence.
class Solution {
public int longestPalindromeSubseq(String s) {
int l = s.length();
//row number is the start of string
//col number is the end of string
var dp = new int[l][l];
//fill equal. if i==i, value is 1.
for (int i=0; i<l; i++) dp[i][i]=1;
for (int i=l-1; i>=0; i--) {
for (int j=i+1; j<l; j++) {
//if end char is the same as the start char, at least get 2
if (s.charAt(i)==s.charAt(j)) {
if (j-i ==1) {
dp[i][j]=2;
} else {
dp[i][j] = 2 + dp[i+1][j-1];
}
} else {
//not equals, we can drop one char from one of the end
//and use the max value of this two casess
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
}
}
}
return dp[0][l-1];
}
}
deep first search
It can be used to traverse graph including binary tree.
//Leetcode 1971
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
// store vetexs where one vetex can go
var map = new HashMap<Integer, ArrayList<Integer>>();
//populate map. Because it is a bi-directional graph,
//need to populate both end of the edge
for(int[] e: edges) {
if (map.containsKey(e[0])) {
var list = map.get(e[0]);
list.add(e[1]);
map.put(e[0], list);
} else {
var list = new ArrayList<Integer>();
list.add(e[1]);
map.put(e[0], list);
}
// the other direction
if (map.containsKey(e[1])) {
var list = map.get(e[1]);
list.add(e[0]);
map.put(e[1], list);
} else {
var list = new ArrayList<Integer>();
list.add(e[0]);
map.put(e[1], list);
}
}
//visited map to remember if this vertex has been visited
var visited = new HashMap<Integer, Integer>();
//store vetexs to visit
var stack = new Stack<Integer>();
//start
stack.add(source);
//do dfs search
while (!stack.isEmpty()) {
int cur = stack.pop();
//only not visited node is to be processed.
//in the other hand, if the vetex has been visited,
//it will be pop out stack and do nothing with it
if (!visited.containsKey(cur)) {
//step one: mark as visited
visited.put(cur, 1);
//step two: check if it is the destination
if (cur == destination) return true;
//step three: put all adjacent vetexs into stack
if (map.containsKey(cur)) {
var aEdges = map.get(cur);
for (int e: aEdges) {
stack.add(e);
}
}
}
}
return false;
}
}
Recursive version of dfs
//Leetcode 1971
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
// store adjecent edges
var map = new HashMap<Integer, ArrayList<Integer>>();
//populate map
for(int[] e: edges) {
if (!map.containsKey(e[0])) {
map.put(e[0], new ArrayList<Integer>());
}
map.get(e[0]).add(e[1]);
if (!map.containsKey(e[1])) {
map.put(e[1], new ArrayList<Integer>());
}
map.get(e[1]).add(e[0]);
}
return dfs(map, source, destination, new HashSet<Integer>());
}
public boolean dfs(HashMap<Integer, ArrayList<Integer>> map, int source, int destination, HashSet<Integer> visited) {
if (source==destination) return true;
//has visited all
if (map.size()==visited.size()) return false;
for(Integer n: map.get(source)) {
if (visited.contains(n)) continue;
//visit n. Then dfs on n
visited.add(n);
if (n==destination) {
return true;
} else {
var ans = dfs(map, n, destination, visited);
if (ans) return true;
}
}
return false;
}
}
Minimum Spanning Tree
Use the Prim-Jarnik algorithm to build a minimum spanning tree. The main idea is to start with a vertex. For every iteration,
try to find a minum weight edege and add that edege to the tree. When we add all vertexs into tree, we are done. Here is an
example to build a tree for a Leetcode problem. We build a tree to find the mininal total weights. LeetCode 1584
LeetCode 1584
class Solution {
public int minCostConnectPoints(int[][] points) {
//pre cal distance between all points
int l = points.length;
int[][]dists = new int[l][l];
for (int i=0; i<l; i++) {
var p = points[i];
for (int j=0; j<l; j++) {
var q = points[j];
dists[i][j] = getDis(p, q);
}
}
int ans =0;
//build tree.
//pick a point as start point for tree. Every time, pick the point which
//has the shortest distance with tree. Need to consider point to the current
//added tree point and points which are in the tree before.
var tree = new HashSet<Integer>();
//store min distance to tree for every points
var disToTree = new int[l];
for (int i=0; i<l; i++) disToTree[i] =Integer.MAX_VALUE;
//add first point as base
var cur = 0;
tree.add(0);
//update dis for point 0
disToTree[0] = 0;
while (tree.size()<l) {
//store possible selected point and min distance so far
int selectedP = 0;
int minDis = Integer.MAX_VALUE;
for (int i=0; i<l; i++) {
//if this point is in the tree, skip
if (tree.contains(i)) continue;
//calculate distance between current tree point and candidate
//update tree distnace for i
int cost = dists[cur][i];
disToTree[i] = Math.min(cost, disToTree[i]);
//if we get smaller distance, update candidate
if (disToTree[i] < minDis) {
minDis = disToTree[i];
selectedP = i;
}
}
//update tree
tree.add(selectedP);
//update ans
ans = ans + minDis;
//update current vetex
cur = selectedP;
}
return ans;
}
//cal distance between two points
private int getDis(int[]p, int[]q) {
return Math.abs(p[0] - q[0]) + Math.abs(p[1] - q[1]);
}
}
Union Find
Find which group a set should be in; then union disjoint-set data. Union Find
//LeetCode 1202
class Solution {
//store parents for every index of string
int[] parent;
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int n = s.length();
parent = new int[n];
//set parent of every index to be itself
for (int i=0; i<n; i++) parent[i]=i;
//do union find. Use find function to find parent of a swap list.
//then union them
for (List pair: pairs) {
var p1 = find((int)pair.get(0));
var p2 = find((int)pair.get(1));
if (p1>=p2) {
parent[p1] = parent[p2];
} else {
parent[p2] = parent[p1];
}
}
//we use some short cut to do union and not a strictly union find
//we need to update parent array once to solve the short cut problem
//this is not a necessary step for other union find problem
for (int i=0; i<n; i++) {
parent[i] =find(parent[i]);
}
//use a hashMap to group indexes which has the same parent
//the values are stored in a tree set, so it is sorted
var groups = new HashMap<Integer, TreeSet<Integer>>();
for (int i=0; i<n; i++) {
int p = parent[i];
if (groups.containsKey(p)) {
var set = groups.get(p);
set.add(i);
groups.put(p, set);
} else {
var set = new TreeSet();
set.add(i);
groups.put(p,set);
}
}
//handle string. For every groups, all chars can be swaped with each other.
//then we find chars in the same group, sort them, and put them back
var ans = new char[n];
for (int key: groups.keySet()) {
var set = groups.get(key);
//get char array
var arr = new char[set.size()];
int c = 0;
for (Integer h: set) {
arr[c] = s.charAt((int)h);
c++;
}
Arrays.sort(arr);
//put back char into original string
c=0;
for (Integer h: set) {
ans[(int)h] = arr[c];
c++;
}
}
//convert array back to string
var sb = new StringBuilder("");
for (char c: ans) sb.append(c);
return sb.toString();
}
//this find function to find parenet of a index recursively
private int find(int a) {
if (parent[a] == a)
return a;
parent[a] = find(parent[a]);
return parent[a];
}
}
Dijkstra's Algorithm to solve the shortest path problem
//Leetcode 1631
class Solution {
int[][] d;
PriorityQueue<int[]> q;
HashSet<Integer> set;
int r;
int c;
int[][] myHeights;
/**
* use Dijkstra's Algorithm. Here v is (0,0) of matrix. Will calculate the shortest
* distance from every point (u) to this v.
*/
public int minimumEffortPath(int[][] heights) {
//step one: initiate values. for 0, 0 distance is 0 for other, dist is max integer val
var max = Integer.MAX_VALUE;
r = heights.length;
c = heights[0].length;
myHeights = heights;
d = new int[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++)
d[i][j] = max;
}
d[0][0] = 0;
//step two, put D[u] into a priority queue. q's key is int[3] ({value, i, j})
//it uses the first value of array to do comparation. This value is the distance
//between u and v
q = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int[] key = { d[i][j], i, j };
q.add(key);
}
}
//step three: set up a set to remember our current cloud. use a interger of postion
//to represent a vertex in matrix. For example, for matrix[3*3], (0,0) has value
//of 0, (3,3) has value of 8
set = new HashSet<Integer>();
//step four: loop until every vertex is in the set
while (set.size() != r * c) {
var point = q.poll();
// put this vertex into our cloud
set.add(point[1] * c + point[2]);
// try to update value for the adjecent vertexs. Try to left, right, up and down
var row = point[1];
var col = point[2];
update(point, row - 1, col);
update(point, row + 1, col);
update(point, row, col - 1);
update(point, row, col + 1);
}
return d[r - 1][c - 1];
}
//used to update distance for adjecent points
public void update(int[] point, int x, int y) {
//if point is in our current cloud, do nothing. If point is in outside matrix, do nothing.
if (set.contains(x * c + y)) return;
if (x < 0 || x >= r) return;
if (y < 0 || y >= c) return;
// this is height of this point
var h = myHeights[point[1]][point[2]];
//calculate new distince for D if we want to go to v by current picked point
var newVal = Math.max(point[0], Math.abs(h - myHeights[x][y]));
var oldVal = d[x][y];
//only need to update if we get shorter path
if (newVal < oldVal) {
d[x][y] = newVal;
int[] key = { newVal, x, y };
q.add(key);
}
}
}