# 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 15 Binarysearch Problems

### 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 10 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 | #bfs, #backtracking, #string | Leetcode: Word Ladder |

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

5 | Remove Comments | #array, #string | Leetcode: Remove Comments |

6 | Split Concatenated Strings | #greedy, #string | Leetcode: Split Concatenated Strings |

7 | Vowel Spellchecker | #hashmap, #string | Leetcode: Vowel Spellchecker |

### 1.7 Top 5 Array Problems

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

1 | Transpose Matrix | #array | Leetcode: Transpose Matrix |

2 | Largest 1-Bordered Square | #graph, #array | Leetcode: Largest 1-Bordered Square |

3 | Alphabet Board Path | #graph, #array | Leetcode: Alphabet Board Path |

### 1.8 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.9 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 |

8 | Sum of Subsequence Widths | #math | Leetcode: Sum of Subsequence Widths |

9 | Remove 9 | #baseconversion, #math | Leetcode: Remove 9 |

### 1.10 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 |

5 | Split Concatenated Strings | #string, #greedy | Leetcode: Split Concatenated Strings |

### 1.11 Top 5 Knapsack Problems

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

1 | Knapsack problem to maximize benefits | #knapsack, #dynamicprogramming | Leetcode: Coin Change |

2 | Get two subset with the same sum | #knapsack, #dynamicprogramming | Leetcode: Tallest Billboard |

### 1.12 Top 5 Montone Stack/Queue Problems

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

1 | Monotone stack for consecutive subarrays | #montone | Leetcode: Online Stock Span, Leetcode: Sum of Subarray Minimums |

2 | Shortest Subarray with Sum at Least K | #montone | Leetcode: Shortest Subarray with Sum at Least K |

### 1.13 Top 20 Object-Oriented Design Problems

### 1.14 Top 50 General Problems

### 1.15 Basic Thinking Methodologies

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

1 | Trial and error | |

2 | Divide and Conquer | |

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

### 1.16 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.17 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 left half | Leetcode: Longest Chunked Palindrome Decomposition |

27 | Use queue to keep flipping the orders | Leetcode: Zigzag Iterator |

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

29 | Avoid unnecessary precheck | |

30 | One pass instead of two pass | |

31 | Swiping line algorithm | |

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

33 | Hide details which are irrelevant |

### 1.18 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.19 More Data Structure

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

Tree map | |

Inverted Index |

### 1.20 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.21 More Resources

License: Code is licensed under MIT License.

https://en.wikipedia.org/wiki/Data_structure

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

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