# Cheatsheet: Leetcode Common Templates & Common Code Problems

- PDF Link: cheatsheet-leetcode-A4.pdf, Category: languages
- Blog URL: https://cheatsheet.dennyzhang.com/cheatsheet-leetcode-A4
- Related posts: CheatSheet: System Design For Code Interview, #denny-cheatsheets

### 1.1 Top 25 Code Templates

### 1.2 Top 20 Graph Problems

Num | Problem | Category/Tag | Summary |
---|---|---|---|

1 | Graph Connectivity: Count islands in a 2D matrix | #dfs, #unionfind | Leetcode: Number of Islands, Leetcode: Island Perimeter |

2 | Get the size of the largest island | #dfs | Leetcode: Max Area of Island |

3 | Cycle detection in an undirected graph | ||

4 | Cycle detection in a directed graph | Leetcode: Redundant Connection II | |

5 | Whether a graph is a tree | #unionfind, #bfs | Leetcode: Graph Valid Tree |

6 | Kruskal’s algorithm: Minimum spanning tree of a weighted graph | #unionfind | Leetcode: Connecting Cities With Minimum Cost |

7 | Dijkstra’s algorithm: shortest path for two nodes in a weighted graph | ||

8 | Floyd-Warshall algorithm: find shortest paths in a weighted graph | #dfs, #dynamicprogramming | |

9 | Update a specific region | #dfs | Leetcode: Flood Fill |

10 | Update regions for a given rule | Leetcode: Surrounded Regions | |

11 | Mark levels | Leetcode: 01 Matrix | |

12 | Duplicate edges | Leetcode: Reconstruct Itinerary | |

13 | Find a certain node in a graph | #unionfind | Leetcode: Find the Celebrity |

14 | Find a certain path from source to destination in a graph | Leetcode: Path With Maximum Minimum Value | |

15 | Find the minimum steps from point1 to point2 | Leetcode: Word Ladder, Leetcode: Sliding Puzzle | |

16 | Find all minimum paths from point1 to point2 | Leetcode: Word Ladder II | |

17 | All Paths from Source Lead to Destination | Leetcode: All Paths from Source Lead to Destination | |

18 | |||

19 | |||

20 |

### 1.3 Top 5 Binarysearch Problems

Num | Problem | Category/Tag | Summary |
---|---|---|---|

1 | Find a first failing version | Leetcode: First Bad Version | |

2 | Search Insert Position | Leetcode: Search Insert Position, Leetcode: Time Based Key-Value Store | |

3 | |||

4 | |||

5 |

### 1.4 Top 10 Dynamic Programming Problems

Num | Problem | Category/Tag | Summary |
---|---|---|---|

1 | LCS – Longest Common Subsequence | #editdistance, #lcs | Leetcode: Longest Common Subsequence |

2 | LIS – Longest increasing subsequence | #string, #lis | Leetcode: Longest Increasing Subsequence |

3 | Edit distance of two strings | #editdistance | Leetcode: Edit Distance |

4 | Maximum subarray problem | #maxsubarraysum | Leetcode: Maximum Subarray |

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 |

### 1.5 Top 10 BinaryTree Problems

Num | Problem | Category/Tag | Summary |
---|---|---|---|

1 | Binary Tree Level Order Traversal | #bfs | Leetcode: Binary Tree Right Side View |

2 | Height of binary tree | #dfs | Leetcode: Balanced Binary Tree |

3 | LCA – Lowest Common Ancestor of a binary Tree | #dfs | Leetcode: Lowest Common Ancestor of a Binary Tree |

4 | Construct binary tree | Leetcode: Construct Binary Tree from Preorder and Postorder Traversal | |

5 | Check whether a binary tree is a full binary tree | #dfs, #bfs | |

6 | Right view of a tree | ||

7 | |||

8 | |||

9 | |||

10 |

### 1.6 Top 5 String Problems

Num | Problem | Category/Tag | Summary |
---|---|---|---|

1 | Edit distance of two strings | #editdistance | Leetcode: Edit Distance |

2 | Remove duplicate letters | #greedy, #stack | Remove Duplicate Letters |

3 | |||

4 | |||

5 |

### 1.7 Top 5 Math Problems

Num | Problem | Category/Tag | Summary |
---|---|---|---|

1 | Check prime – Sieve of Eratosthenes | #prime | Leetcode: Count Primes |

2 | Check leap year | #leapyear | Leetcode: Day of the Week |

3 | Rectangle | #rectangle | |

4 | gcd | #gcd | |

5 |

### 1.8 Top 45 General Problems

### 1.9 Common Tips For Clean Code

Num | Name | Summary |
---|---|---|

1 | Caculate sum of a range quickly | #presum,Leetcode: Maximum Subarray |

2 | Move in four directions for a matrix | Leetcode: Sliding Puzzle |

3 | Split string by multiple seperator | Leetcode: Brace Expansion |

4 | Add a dummy tailing element to simplify code | Leetcode: Brace Expansion |

5 | Fast slow pointers | LintCode: Middle of Linked List |

6 | Deep copy an array | Leetcode: Combination Sum |

7 | Use arrays instead of hashmaps, if possible | Leetcode: Number of Days in a Month |

8 | Control the order of dfs | Leetcode: Subsets II |

9 | Avoid inserting into the head of an array | Leetcode: Path In Zigzag Labelled Binary Tree |

10 | From right to left, instead of left to right | Leetcode: Merge Sorted Array |

11 | Think the other way around | `Add Items` vs `Remove Items` , `Increase Counter` vs `Decrease Counter` |

12 | Avoid uncessary if…else… | res[i] = (diff/2 <= k), Leetcode: Can Make Palindrome from Substring |

13 | To get the case of K, solve: at most K – at most (K-1) | Leetcode: Subarrays with K Different Integers |

14 | Instead of deleting entry from hashmap, decrease counter | Leetcode: Longest Substring with At Most K Distinct Characters |

15 | Find the max/min; If not found, return 0 | Leetcode: Minimum Area Rectangle |

16 | With helper function vs without helper function | Leetcode: Longest Repeating Character Replacement |

17 | Instead of adding a character, try to delete one | Leetcode: Longest String Chain |

18 | #roudtrippass: from left to right, then right to left | Leetcode: Shortest Distance to a Character |

19 | Delayed caculation to simplify the code | Leetcode: Interval List Intersections |

20 | Instead of removing, add padding elements | Leetcode: Duplicate Zeros |

21 | Initialize array with n+1 length to simplify code | Leetcode: Range Addition |

22 | To avoid pointer get polluted by i++/i–, use l[i+1]/l[i-1] | Leetcode: Previous Permutation With One Swap |

23 | Hashmap can reduce caculation, but may complicate things too | Leetcode: Maximum Frequency Stack |

24 | Avoid unnecessary precheck | |

25 | One pass instead of two pass | |

26 | Swiping line algorithm | |

27 | Add a dummy head node for linked list | |

28 | Hide details which are irrelevant | |

29 | Avoid delete element from hashmaps |

### 1.10 Golang Tips

Name | Summary |
---|---|

Golang return a tuple | `func dfs(root *TreeNode, max *float64) (sum int, cnt int)` , Leetcode: Maximum Average Subtree |

Use strings.Builder, instead of string | Leetcode: Unique Email Addresses |

Variable Conversion | `float64(x_int/y_int)` != `float64(x_int)/float64(y_int)` , Leetcode: Maximum Average Subtree |

For a list of objects, pass by value or reference | `f(l []*TreeNode)` vs `f(l *[]*TreeNode)` , Leetcode: Lowest Common Ancestor of a Binary Tree |

### 1.11 Resource For Code Problems

Name | Summary |
---|---|

Leetcode summary | Link: Top Google Questions, Link: Top 100 Liked Questions, Link: Top Interview Questions |

Leetcode summary | GitHub: kdn251/interviews |

Leetcoder on YouTube | lee 215, Aoxiang Cui |

Online test websites | spoj.com, Google – codejam |

Online test websites | hackerrank.com, hackerrank – hard |

Online test websites | codeforces.com, poj.org |

Online test websites | acm.hdu.edu.cn, acm.zju.edu.cn, acm.timus.ru, uva.onlinejudge.org |

visualgo | visualising data structures and algorithms through animation |

Reference | geeksforgeeks.org |

Reference | Youtube: Abdul Bari – Algorithm |

### 1.12 More Resources

License: Code is licensed under MIT License.

https://www.cs.princeton.edu/~rs/AlgsDS07/

https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/