Algorithm general templates

Tree traverse

void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    traverse(root.right);
}

Graph traverse

void traverse(Node root) {
   if (root == null) return;
   for (Node child : root.children) {
      traverse(child);
   }
}

Graph DFS traverse

boolean[] visited = new boolean[len];
void traverse(Graph graph, int v) {
    if (visited[v]) return;
    visited[v] = true;
    for (Node neighbor : graph.neighbors(v)) {
        traverse(graph, neighbor);
    }
}

void traverse2(Graph graph, int v) {
    visited[v] = true;
    for (int neighbor : graph.neighors(v)) {
        if (!visited[neighbor]) {
            traverse(neighbor);
        }
    }
}

Binary Search

    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int left =0, right = nums.length - 1;
        while(left <= right){
            int middle = left + (rigth - left) / 2;
            if(nums[middle] == target) return middle; //f(x)
            if(nums[middle] > target){ // g(x)
                right = middle - 1;
            } else{
                left = middle + 1;
            }
        }
        // left is the smallest index which satisfice g(x)
        // in this case, left is upper bond
        return -1;
    }
    
    int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // Don't return, but move right pointer closer
                right = mid - 1;
            }
        }
        // Check if left point exceeded the bound 
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }
    
    public static int findLeftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                // Condition is not satisfied, left bound must be to the right of mid
                left = mid + 1;
            } else {
                // Condition is satisfied, left bound must be at or to the left of mid
                right = mid;
            }
        }

        return left;
    }
    
    int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // Don't return, but move left pointer further
                left = mid + 1;
            }
        }
        // Check if the right pointer exceeded the bound
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }
    
    public static int findRightBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] <= target) {
                // Condition is satisfied, right bound must be to the right of mid
                left = mid + 1;
            } else {
                // Condition is not satisfied, right bound must be to the left of mid
                right = mid;
            }
        }

        return left;
    }

Sliding Window (Two pointers)

public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if(s == null || s.length() == 0){
            return 0;
        }
        int start = 0, end = 0;
        int count = 0, max = 0;
        int[] charMap = new int[128];
        while(end < s.length()){
            // increase end pointer and count for char at end
            // increase the window
            if(charMap[s.charAt(end++)]++ == 0){
                count++;
            }
            // while conditions not met, move start pointer
            //shrink the window
            while(count > k){
                if(charMap[s.charAt(start++)]-- == 1){
                    count--;
                }
            }
            // calculate max for all valid conditions
            max = Math.max(max, end - start);
        }

        return max;
}

Tree

Inorder traversal a Binary Search Tree with iteration which will get a sorted array.

public List<Integer> inorderTraverse(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) { 
        return list;
    }
    
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;

    }
    return list;
}

Preorder traverse binary tree using iteration way

public List<Integer> preorderTraverse(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  if (root == null) {
     return result;
  }
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  while (!stack.isEmpty()) {
     TreeNode curNode = stack.pop();
     result.add(curNode.val);
     if (curNode.right != null) {
        stack.push(curNode.right);
     }
     if (curNode.left != null) {
        stack.push(curNode.left);
     }
  }
  return result;
}

Postorder traverse binary tree using iteration way

public List<Integer> postorderTraverse(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode curNode = stack.pop();
        result.add(0, curNode.val);
        if (curNode.left != null) {
           stack.push(curNode.left);
        }
        if (curNode.right != null) {
            stack.push(curNode.right);
        }
    }
    return result;
}

Find all ancestors for a node

List<TreeNode> ancestors = new ArrayList<>();
public boolean findAllAncestors(TreeNode root, TreeNode target) {
        if (root == null) return false;
        if (root == target) return true;
        boolean left = findAncestors(root.left, target);
        boolean right = findAncestors(root.right, target);
        if (left || right) {
            ancestors.add(root);
        }
        return left || right;
    }

BST

//Template1 of finding items in Binary search tree
void BST(TreeNode root, int target) {
    if (root.val == target)
        //find the item
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

//Valid BST
 public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) {
            return true;
        }
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;

        return isValidBST(root.left, min ,root) && isValidBST(root.right, root, max);

    }

Back Tracking

//Template

result = List<>
public void backtrack(/path, /choices) {
    if(meet condition) {
        result.add(path);
        return;
    }
    for (choice : choices) {
        make the choice based on path
        backtrack(path, choices);
        reverse the choice
    }
}

Combination

  public static List<List<Integer>> allCombine(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }

    public static void backtrack(List<List<Integer>> result, List<Integer> tmpList, int[] nums, int index) {
        // Make a copy of tmpList
        result.add(new ArrayList<>(tmpList));
        // Loop through all possibilities for next position (Purning)
        for (int i = index; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backtrack(result, tmpList, nums, i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }

Permutation

 public List<List<Integer>> permuteUnique(int[] nums) {
        // Need to srot the array first if it contains the same numbers
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tmp, int[] nums, boolean[] visited){
        // Only add valid list to result
        if(tmp.size() == nums.length){
            result.add(new ArrayList(tmp));
            return;
        }

        for(int i=0; i < nums.length; i++){
            // Do not put the same # at the same position twice
            if(visited[i] || i > 0 && nums[i] == nums[i-1] && !visited[i-1]){
                continue;
            }
            tmp.add(nums[i]);
            visited[i] = true;
            backtrack(result, tmp, nums, visited);
            visited[i] = false;
            tmp.remove(tmp.size() -1);
        }
    }

Graph

BFS

//Simple graph BFS template
private void bfs(int[][] graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w: graph[v]) {
            if (!visited[w]) {
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

Leetcode 286

    public void wallsAndGates(int[][] rooms) {
        if(rooms == null || rooms.length == 0){
            return;
        }
        int m = rooms.length, n = rooms[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(rooms[i][j] == 0){
                    queue.offer(new int[]{i, j, 0});
                }
            }
        }
        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            for(int[] dir : directions){
                int r = cur[0] + dir[0];
                int c = cur[1] + dir[1];
                // out of boundaries
                if(r < 0 || r >= m || c < 0 || c >= n){
                    continue;
                }
                // condition check/check visited or not
                if(rooms[r][c] != Integer.MAX_VALUE){
                    continue;
                }
                // set visted and update node
                rooms[r][c] = cur[2] + 1;
                // add neighbour into queue
                queue.offer(new int[]{r, c, rooms[r][c]});
            }
        }
    }

DFS

Leetcode 733

 public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int color = image[sr][sc];
        // do dfs for each source point
        if(color != newColor)
            dfs(image, sr, sc, color, newColor);
        return image;
    }

    private void dfs(int[][] image, int row, int col,int color, int newColor){
        // if condition do not meet, return
        if(row < 0 || row >= image.length || col < 0 || col >= image[0].length
           || image[row][col] != color){
            return;
        }
        // set visted and operate current point
        image[row][col] = newColor;
        dfs(image, row, col - 1, color, newColor);
        dfs(image, row, col + 1, color, newColor);
        dfs(image, row - 1, col, color, newColor);
        dfs(image, row + 1, col, color, newColor);
    }

Dijkstra

Leetcode 743

 public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for(int[] time : times){
            List<int[]> edges = graph.getOrDefault(time[0], new ArrayList<>());
            edges.add(new int[]{time[1], time[2]});
            graph.put(time[0], edges);
        }
        // target, weight -- use heap to reduce time complexity
        PriorityQueue<int[]> pq = new PriorityQueue<>((n1, n2) -> n1[1] -n2[1]);
        pq.offer(new int[]{K, 0});
        // Init distance map
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        int count = 0;
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            if(dist[cur[0]] < cur[1]) continue;
            count++;
            if(graph.get(cur[0]) != null){
                for(int[] edge : graph.get(cur[0])){
                    int d = cur[1] + edge[1];
                    if(d < dist[edge[0]]){
                        dist[edge[0]] = d;
                        pq.offer(new int[]{edge[0], d});
                    }
                }
            }
        }
        if(count != N) return -1;
        int max = 0;
        for(int i = 1; i <= N; i++){
            max = Math.max(max, dist[i]);
        }

        return max;
    }

Sort algorithms

// Quick sort
public int[] quickSort(int[] array, int l, int h) {
    if (l<h) {
        int partition = partition(array, l, h);
        quickSort(array, l, partition-1);
        quickSort(array, partition+1, h);
    }
}

public void swap (int[] array, i, j) {

}

public int partition(int[] array, int l, int h) {
    int partition = l;
    int pivot = array[h];
    for (int i = l; i < h; i++) {
        if (array[i] <= pivot) {
            swap(array, i, partition);
            partition++;
        }
    }
    swap(array, partition, h);
    return partition;
}


// merge sort
public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];

    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);

    merge(a, l, r, mid, n - mid);
}

public static void merge(
  int[] a, int[] l, int[] r, int left, int right) {
 
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

Toplogical Sort

public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(prerequisites == null || prerequisites.length == 0) return true;

        //Record the indegree num of every cources
        int[] indegrees = new int[numCourses];
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int res = numCourses;

        //set indegree and build graph
        for (int[] prerequisite :  prerequisites) {
            indegrees[prerequisite[0]]++;
            graph.computeIfAbsent(prerequisite[1], k -> new ArrayList<>()).add(prerequisite[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }
        
        //BFS on the courses with 0 indegree, add the new cources to the queue if indegree is 0
        while (!queue.isEmpty()) {
            int cource = queue.poll();
            res--;
            if (graph.get(cource) != null) {
                for (int node : graph.get(cource)) {
                    indegrees[node]--;
                    if (indegrees[node] == 0) {
                        queue.offer(node);
                    }
                }
            }
        }

        return res == 0;

    }

Union Find

//without rank
int[] parents
void Union(int p, int q) { 
   parents[find(p)] = find(q); 
}

public int find(int i){
    if(parents[i] == i){
        return i;
    }
    return parents[i] = find(parents[i]);
}

public UnionFind(int n){
    parents = new int[n];
    for(int i = 0; i < n; i++){
        parents[i] = i;
    }
}

//With rank
class UnionFind{
    int[] parents;
    int[] ranks;

    public UnionFind(int n){
        parents = new int[n];
        ranks = new int[n];
        for(int i = 0; i < n; i++){
            parents[i] = i;
        }
    }

    public int find(int i){
        if(parents[i] == i){
            return i;
        }
        return parents[i] = find(parents[i]);
    }

    public void union(int a, int b){
        int root1 = find(a);
        int root2 = find(b);
        if(root1 == root2){
            return;
        }
        if(ranks[root1] < ranks[root2]){
            parents[root1] = root2;
        }else if(ranks[root2] < ranks[root1]){
            parents[root2] = root1;
        }else{
            parents[root2] = root1;
            ranks[root1]++;
        }
    }

}

Trie

class TrieNode{
    Map<Character, TrieNode> children;
    boolean isWord;

    public TrieNode(){
        children = new HashMap<>();
    }
}

class Trie{
    TrieNode root;

    public Tire(){
        root = new TrieNode();
    }

    public void insert(String word){
        TrieNode p = root;
        for(char c : word.toCharArray()){
            p.children.computeIfAbsent(c, k -> new TrieNode());
            p = p.children.get(c);
        }
        p.isWord = true;
    }

    public TrieNode find(String prefix){
        TrieNode p = root;
        for(char c : prefix.toCharArray()){
            if(p.children.get(c) == null){
                return null;
            }
            p = p.children.get(c);
        }

        return p;
    }
    
}

Word Dictionary with . wildchards matching

class WordDictionary {

    class TrieNode {
        TrieNode[] children;
        boolean isWord;
        TrieNode() {
            children = new TrieNode[26];
            isWord = false;
        }
    }

    TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode curNode = root;
        for (char ch : word.toCharArray()) {
            int charIndex = ch - 'a';
            if (curNode.children[charIndex] == null) {
                curNode.children[charIndex] = new TrieNode();
            }
            curNode = curNode.children[charIndex];
        }
        curNode.isWord = true;
    }
    
    public boolean search(String word) {
       return find(word, root, 0);
    }

    //Need DFS search, because of wildcard matching
    private boolean find(String word, TrieNode startNode, int index) {
        if (index == word.length()) {
            return startNode.isWord;
        }
        char ch = word.charAt(index);
        if (ch != '.') {
            int charIndex = ch - 'a';
            return startNode.children[charIndex] != null && find(word, startNode.children[charIndex], index + 1);
        } else {
            for (TrieNode node : startNode.children) {
                if (node != null && find(word, node, index + 1)) {
                    return true;
                }
            }
            return false;
        }
    }
}

Segment Tree

class SegmentTreeNode{
    int start;
    int end;
    int sum;
    SegmentTreeNode left;
    SegmentTreeNode right;

	public SegmentTreeNode(int start, int end){
        this.start = start;
        this.end = end;
    }

    private SegmentTreeNode buildTree(int start, int end, int[] nums){
	    if(start > end) return null;
        SegmentTreeNode node = new SegmentTreeNode(start, end);
 	    if(start == end){
	        node.sum = nums[start];
	        return node;
        } else {
            int mid = start + (end - start)/2;
            node.left = buildTree(start, mid, nums);
            node.right = buildTree(mid + 1, end, nums);
	        node.sum = node.left.sum + node.right.sum;
        }

        return node;
    }

    private void updateNode(SegmentTreeNode node, int index, int val){
	    if(node.start == node.end){
	        node.sum = val;
	        return;
        }
        int mid = node.start + (node.end - node.start)/2;
        if(mid >= index){
            updateNode(node.left, index, val);
        }else{
            updateNode(node.right, index, val);
        }
        node.sum = node.left.sum + node.right.sum;
    }

    private int sumRange(SegmentTreeNode node, int start, int end){
	    if(node.start == start && node.end == end){
	        return node.sum;
        }
        int mid = node.start + (node.end - node.start)/2;
        if(start > mid){
	        return sumRange(node.right, start, end);
        }else if(end <= mid){
	        return sumRange(node.left, start, end);
        }else{
            return sumRange(node.left, start, mid) + sumRange(node.right, mid + 1, end);
        }
    }
}

Typical Tree Recursion subproblem (use postorder)

//Diameter of a tree
//https://leetcode.com/problems/diameter-of-binary-tree/
int maxDiameter = 0;
public int diameter(TreeNode root) {
    maxDepth(root);
    return maxDiameter;
}
private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftMaxDepth = maxDepth(root.left);
    int rightMaxDepth = maxDepth(root.right);
    maxDiameter = Math.max(maxDiameter, leftMaxDepth + rightMaxDepth);
    return Math.max(leftMaxDepth, rightMaxDepth) + 1;
}
/********************************/


//Max path sum of a tree
int maxPathSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    maxSingleSidePathSum(root);
    return maxPathSum;
}
private int maxSingleSidePathSum(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftPathSum = Math.max(0, maxSingleSidePathSum(root.left));
    int rightPathSum = Math.max(0, maxSingleSidePathSum(root.right));
    maxPathSum = Math.max(maxPathSum, leftPathSum + rightPathSum + root.val);
    return Math.max(leftPathSum, rightPathSum) + root.val;
}