# 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 30 Graph Problems

Num | Problem | Summary |
---|---|---|

1 | Graph Connectivity: Count islands in a 2D matrix | LeetCode: Number of Islands, LeetCode: Island Perimeter |

2 | Get the size of the largest island | LeetCode: Max Area of Island |

3 | Find shortest distance for two nodes in an undirected graph | |

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

5 | Detect all cycles in a directed graph | LeetCode: Find Eventual Safe States |

6 | Whether a graph is a tree | LeetCode: Graph Valid Tree |

7 | Minimum Spanning Tree(MST) of a weighted graph – Kruskal’s algorithm | LeetCode: Connecting Cities With Minimum Cost |

8 | Find shortest paths in a weighted graph – Floyd-Warshall algorithm | |

9 | Shortest path for two nodes in a weighted graph – Dijkstra’s algorithm | LeetCode: Connecting Cities With Minimum Cost |

10 | Update a specific region | LeetCode: Flood Fill |

11 | Update regions for a given rule | LeetCode: Surrounded Regions |

12 | Number of Distinct Islands | LeetCode: Number of Distinct Islands |

13 | Mark levels | LeetCode: 01 Matrix |

14 | Diameter of a tree in graph theory | LeetCode: Tree Diameter |

15 | Duplicate edges | LeetCode: Reconstruct Itinerary |

16 | Find a certain node in a graph | LeetCode: Find the Celebrity |

17 | Coloring graph | LeetCode: Minesweeper |

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

19 | Find the minimum steps from point1 to point2 | LeetCode: Word Ladder, LeetCode: Sliding Puzzle |

20 | Find all minimum paths from point1 to point2 | LeetCode: Word Ladder II |

21 | All Paths from Source Lead to Destination | LeetCode: All Paths from Source Lead to Destination |

22 | Node connectivity problem for a sparse 2D matrix | LeetCode: Escape a Large Maze |

23 | Bricks Falling When Hit | LeetCode: Bricks Falling When Hit |

24 | Bridges in a connected graph – Tarjan’s algorithm | LeetCode: Critical Connections in a Network |

25 | Valid & Invalid moves | LeetCode: Alphabet Board Path |

26 | Move in different directions: 4 directions, 8 directions | LeetCode: Queens That Can Attack the King |

27 | String Transforms Into Another String | LeetCode: String Transforms Into Another String |

### 1.3 Top 20 Binarysearch Problems

### 1.4 Top 25 Dynamic Programming Problems

### 1.5 Top 15 BinaryTree Problems

Num | Problem | Summary |
---|---|---|

1 | Binary Tree Level Order Traversal | LeetCode: Binary Tree Right Side View |

2 | Get binary tree height, width | LeetCode: Balanced Binary Tree |

3 | LCA – Lowest Common Ancestor of a binary Tree | LeetCode: Lowest Common Ancestor of a Binary Tree |

4 | Validate Binary Search Tree | LeetCode: Validate Binary Search Tree |

5 | Construct binary tree | LeetCode: Construct Binary Tree from Preorder and Postorder Traversal |

6 | Distribute Coins in Binary Tree | LeetCode: Distribute Coins in Binary Tree |

7 | Binary Tree Vertical Order Traversal | LeetCode: Binary Tree Vertical Order Traversal |

8 | Verify Preorder Sequence in Binary Search Tree | LeetCode: Verify Preorder Sequence in Binary Search Tree |

9 | Recursive + Greedy | LeetCode: Binary Tree Coloring Game |

10 | Binary tree + greedy | LeetCode: Binary Tree Cameras |

### 1.6 Top 10 String Problems

Num | Problem | Summary |
---|---|---|

1 | Edit distance of two strings | LeetCode: Edit Distance |

2 | Remove duplicate letters | Remove Duplicate Letters |

3 | Word ladder | LeetCode: Word Ladder |

4 | lrs – Longest repeating substring | LeetCode: Longest Repeating Substring |

5 | Remove Comments | LeetCode: Remove Comments |

6 | Split Concatenated Strings | LeetCode: Split Concatenated Strings |

7 | Vowel Spellchecker | LeetCode: Vowel Spellchecker |

8 | Lexicographically minimal string rotation | LeetCode: Last Substring in Lexicographical Order |

9 | String Transforms Into Another String | LeetCode: String Transforms Into Another String |

10 | Find the Closest Palindrome | LeetCode: Find the Closest Palindrome |

### 1.7 Top 5 Array Problems

Num | Problem | Summary |
---|---|---|

1 | Transpose Matrix | LeetCode: Transpose Matrix |

2 | Largest 1-Bordered Square | LeetCode: Largest 1-Bordered Square |

3 | Alphabet Board Path | LeetCode: Alphabet Board Path |

4 | Set Mismatch | LeetCode: Set Mismatch |

5 | Majority Element | LeetCode: Majority Element |

### 1.8 Top 5 Linkedlist Problems

Num | Problem | Summary |
---|---|---|

1 | Merge k Sorted Lists | LeetCode: Merge k Sorted Lists |

2 | Detect cycle for a linked list | LeetCode: Linked List Cycle |

3 | LFU cache with double linkedlist | LeetCode: LFU Cache |

### 1.9 Top 10 Sliding Window Problems

Num | Problem | Summary |
---|---|---|

1 | Sliding window with fixed size | LeetCode: Find All Anagrams in a String |

2 | Sliding window with non-decreasing size | LeetCode: Max Consecutive Ones III |

3 | How to initialize the time window? | LeetCode: Minimum Swaps to Group All 1’s Together |

4 | Sliding window with non-decreasing size | LeetCode: Max Consecutive Ones III |

5 | Move two pointers: two loop vs One loop | LeetCode: Longest Substring Without Repeating Characters |

6 | Inspiring sliding window problem | LeetCode: Moving Stones Until Consecutive II |

7 | Sliding window with adjustable size | |

8 | Move pointer1 to match the other, or the other way around |

### 1.10 Top 10 Math Problems

Num | Problem | Summary |
---|---|---|

1 | Check prime – Sieve of Eratosthenes | LeetCode: Count Primes |

2 | Check leap year | LeetCode: Day of the Week |

3 | GCD | LeetCode: Fraction Addition and Subtraction |

4 | Overlapping area of two rectangles | LeetCode: Rectangle Area |

5 | Rotate Array by k steps | LeetCode: Rotate Array |

6 | Mapping data range of getRand algorithm | LeetCode: Implement Rand10() Using Rand7() |

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

8 | Sum of Subsequence Widths | LeetCode: Sum of Subsequence Widths |

9 | Reduce f(x, y) to g(x) | Leetcode: Maximum of Absolute Value Expression |

10 | Remove 9 | LeetCode: Remove 9 |

11 | Fraction to Recurring Decimal | LeetCode: Fraction to Recurring Decimal |

12 | Check if two line segments intersect |

### 1.11 Top 10 Greedy Problems

Num | Problem | Summary |
---|---|---|

1 | Next Permutation | LeetCode: Next Permutation |

2 | Split Array into Consecutive Subsequences | LeetCode: Split Array into Consecutive Subsequences |

3 | Remove duplicate letters | Remove Duplicate Letters |

4 | Bag of Tokens | LeetCode: Bag of Tokens |

5 | Two City Scheduling | LeetCode: Two City Scheduling |

6 | Split Concatenated Strings | LeetCode: Split Concatenated Strings |

7 | Jump Game II | LeetCode: Jump Game II |

8 | Delete Columns to Make Sorted II | LeetCode: Delete Columns to Make Sorted II |

### 1.12 Top 5 Trie Problems

Num | Problem | Summary |
---|---|---|

1 | Extra datastructure in trie to save caculation | LeetCode: Word Search II |

2 | Trie for bit manipulation | LeetCode: Maximum XOR of Two Numbers in an Array. |

3 | Fuzzy match for trie tree | LeetCode: Implement Magic Dictionary |

### 1.13 Top 5 Union Find Problems

Num | Problem | Summary |
---|---|---|

1 | Union find for weighted graph | LeetCode: Evaluate Division |

2 | Union find: connect groups and merge node count | LeetCode: Bricks Falling When Hit |

### 1.14 Top 5 Heap/Priority Queue Problems

Num | Problem | Summary |
---|---|---|

1 | Meeting Rooms II | LeetCode: Meeting Rooms II |

2 | Task Scheduler | LeetCode: Task Scheduler |

3 | Last Stone Weight | LeetCode: Last Stone Weight |

4 | The Skyline Problem | LeetCode: The Skyline Problem |

### 1.15 Top 5 Montone Stack/Queue Problems

Num | Problem | Summary |
---|---|---|

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

2 | Shortest Subarray with Sum at Least K | LeetCode: Shortest Subarray with Sum at Least K |

### 1.16 Top 10 Backtracking Problems

Num | Problem | Summary |
---|---|---|

1 | Generate unique permutation | LeetCode: Permutations II |

2 | Permutation: All elements must take | LeetCode: Pyramid Transition Matrix |

3 | Combination: All elements can take or don’t take | LeetCode: Subsets II |

4 | Expression Add Operators | LeetCode: Expression Add Operators |

5 | Permutation vs Combination | LeetCode: Campus Bikes II |

6 | Define dfs backtracking function | LeetCode: Verbal Arithmetic Puzzle |

### 1.17 Top 20 Object-Oriented Design Problems

### 1.18 Top 50 General Problems

### 1.19 Basic Thinking Methodologies

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

1 | Trial and error | |

2 | Divide and Conquer | |

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

### 1.20 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 | Treat each point as the last item, instead of the first | LeetCode: Burst Balloons |

4 | Avoid deleting element from hashmaps |

### 1.21 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 | Add a dummy head node for linked list | LeetCode: Reverse Linked List |

30 | Hide details which are irrelevant | |

31 | One pass instead of two pass | |

32 | Avoid unnecessary precheck |

### 1.22 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.23 More Data Structure

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

Tree map | |

Inverted Index |

### 1.24 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.25 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/