# Cheatsheet: Leetcode Common Templates & Common Code Problems

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

### 1.1 Top 25 Code Templates

### 1.2 Top 25 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 | Find shortest distance for two nodes in an undirected graph | #bfs | |

4 | Cycle detection in an undirected graph | ||

5 | Cycle detection in a directed graph | #topologicalsort | Leetcode: Redundant Connection II |

6 | Detect all cycles in a directed graph | #dfs, #bfs | Leetcode: Find Eventual Safe States |

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

8 | Minimum Spanning Tree(MST) of a weighted graph – Kruskal’s algorithm | #unionfind | Leetcode: Connecting Cities With Minimum Cost |

9 | Shortest path for two nodes in a weighted graph – Dijkstra’s algorithm | ||

10 | Find shortest paths in a weighted graph – Floyd-Warshall algorithm | #dfs, #dynamicprogramming | |

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

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

13 | Number of Distinct Islands | #island, #dfs, #hashmap | Leetcode: Number of Distinct Islands |

14 | Mark levels | Leetcode: 01 Matrix | |

15 | Diameter of a tree in graph theory | #dfs, #bfs | Leetcode: Tree Diameter |

16 | Duplicate edges | Leetcode: Reconstruct Itinerary | |

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

18 | Coloring graph | #colorgraph, #bfs, #dfs | Leetcode: Minesweeper |

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

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

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

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

23 | Node connectivity problem for a sparse 2D matrix | #dfs, #bfs | Leetcode: Escape a Large Maze |

24 | Bricks Falling When Hit | #unionfind | Leetcode: Bricks Falling When Hit |

25 | Bridges in a connected graph – Tarjan’s algorithm | Leetcode: Critical Connections in a Network |

### 1.3 Top 10 Binarysearch Problems

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

1 | Find the first true | #binarysearch | Leetcode: First Bad Version |

2 | Find the last true | #binarysearch | Leetcode: Longest Repeating Substring |

3 | Search Insert Position | #binarysearch | Leetcode: Search Insert Position, Leetcode: Time Based Key-Value Store |

4 | Random Point in Non-overlapping Rectangles | #binarysearch | Leetcode: Random Point in Non-overlapping Rectangles |

5 | Binary search on monotonic function | #monotonicfunc, #binarysearch | Leetcode: Sqrt(x), Leetcode: Capacity To Ship Packages Within D Days |

6 | Place k elements to minimize max distance | #monotonicfunc, #float | Leetcode: Minimize Max Distance to Gas Station |

7 | Missing Element in Sorted Array | #binarysearch | Leetcode: Missing Element in Sorted Array |

8 | Kth Smallest Number in Multiplication Table | #monotonicfunc, #binarysearch | Leetcode: Kth Smallest Number in Multiplication Table |

### 1.4 Top 15 Dynamic Programming Problems

### 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 | Get binary tree height, width | #dfs | Leetcode: Balanced Binary Tree |

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

4 | Validate Binary Search Tree | #dfs | Leetcode: Validate Binary Search Tree |

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

6 | Right view of a tree | ||

7 | Longest path inside a binary tree | ||

8 | Biggest path sum inside a binary tree | ||

9 | Implement a getNext iterator of in-order trasversal | ||

10 | Construct binary tree | #recursive | Leetcode: Construct Binary Tree from Preorder and Postorder Traversal |

### 1.6 Top 5 String Problems

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

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

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

3 | Word ladder | #string, #bfs, #backtracking | Leetcode: Word Ladder |

4 | lrs – Longest repeating substring | #lrs, #rollinghash | Leetcode: Longest Repeating Substring |

### 1.7 Top 5 Linkedlist Problems

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

1 | Merge k Sorted Lists | #linkedlist, #heap | Leetcode: Merge k Sorted Lists |

2 | Detect cycle for a linked list | #twopointer, #linkedlist | Leetcode: Linked List Cycle |

3 | LFU cache with double linkedlist | #lfu, #linkedlist | Leetcode: LFU Cache |

### 1.8 Top 10 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 | GCD | #gcd | |

4 | Rectangle | #rectangle | |

5 | Rotate Array by k steps | #rotatelist | Leetcode: Rotate Array |

6 | Mapping data range of getRand algorithm | #random | Leetcode: Implement Rand10() Using Rand7() |

7 | Deal with float | #float | Leetcode: Minimize Max Distance to Gas Station |

### 1.9 Top 5 Greedy Problems

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

1 | Next Permutation | #nextpermutation, #greedy | Leetcode: Next Permutation |

2 | Split Array into Consecutive Subsequences | #splitarray, #greedy | Leetcode: Split Array into Consecutive Subsequences |

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

4 | Two City Scheduling | #greedy | Leetcode: Two City Scheduling |

### 1.10 Top 20 Object-Oriented Design Problems

### 1.11 Top 50 General Problems

### 1.12 Basic Thinking Methodologies

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

1 | Trial and error | |

2 | Divide and Conquer | |

3 | Start with naive algorithm, then identify useless steps |

### 1.13 Tips: Think From The Other Direction

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

1 | In graph, instead of deleting edges, add edge in reverse | Leetcode: Bricks Falling When Hit |

2 | Instead of BFS from empty to islands, do the otherwise | Leetcode: As Far from Land as Possible |

3 | Avoid deleting element from hashmaps |

### 1.14 Common Tips For Clean Code

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

1 | Calculate 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 separators | 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 unnecessary 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 calculation 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 | Look for off-by-one errors, sometimes use i+1<len(l) vs i<len(l) | Leetcode: Previous Permutation With One Swap |

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

24 | Sliding window to get the longest size of subarray | Leetcode: Max Consecutive Ones III |

25 | In matrix dfs, change cell to impossible value to avoid state hashmap | Leetcode: Word Search II |

26 | For palindrome check, check the whole string, instead of the left half | Leetcode: Longest Chunked Palindrome Decomposition |

27 | Find a pair with sum meets some requirements | Leetcode: Two Sum |

28 | Avoid unnecessary precheck | |

29 | One pass instead of two pass | |

30 | Swiping line algorithm | |

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

32 | Hide details which are irrelevant |

### 1.15 Whiteboard Tips

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

Focus on your key motivations or thinkings | Pivot quickly from interviewers’ feedback |

Brute force algorithm add values | Intuitive algorithms are usually the starting points of optimal ones |

Work through specific test case clearly | Reduce bugs, and help to obtain interviewers’ feedback early |

Naming variables could be tricky | Settle down a set of variables per your preference |

You don’t have to crack all problems/optimal algorithms |

### 1.16 More Data Structure

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

Tree map | |

Inverted Index |

### 1.17 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, Github: Algorithms-and-Coding-Interviews |

YouTube | How to: Work at Google – Example Coding/Engineering Interview, lee 215, Aoxiang Cui, happygirlzt |

Online test websites | hihocoder.com, codeforces.com, spoj.com, Google – codejam, hackerrank.com |

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

visualgo | visualizing data structures and algorithms through animation |

Reference | geeksforgeeks.org, Youtube: Abdul Bari – Algorithm |

Reference | COS 423 Theory of Algorithms |

### 1.18 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/