Using CheatSheets To Apply Best Practices

Cheatsheet: Leetcode Common Templates & Common Code Problems

Cheatsheet: Leetcode Common Templates & Common Code Problems

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      

https://code.dennyzhang.com

denny_leetcode.png

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

Num Problem Category/Tag Example
1 Seperate a list into several groups #groupelements, #twopointer Leetcode: Summary Ranges
2 Split string #string Leetcode: License Key Formatting
3 TopK problem #heap, #topk Leetcode: Top K Frequent Elements, Leetcode: Find K Pairs with Smallest Sums
4 Sort one array based on another array #sortbyfunction Leetcode: Relative Sort Array
5 Longest substring with at most K distinct characters #slidingwindow, #atmostkdistinct Leetcode: Longest Substring with At Most K Distinct Characters
6 Longest subarray with maximum K 0s #slidingwindow Leetcode: Max Consecutive Ones III
7 Next Permutation #greedy, #nextpermutation Leetcode: Next Permutation
8 Range update with lazy propagation #combinedcaculation, #rangesum Leetcode: Corporate Flight Bookings
9 Monotone stack for consecutive subarrays #montone Leetcode: Online Stock Span, Leetcode: Sum of Subarray Minimums
10 Get all possibilities of subsets #subset, #backtracking Leetcode: Subsets II, Leetcode: Subsets
11 Choose k numbers from a list #combination, #backtracking Leetcode: Combination Sum II
12 Combination from multiple segments #combination, #backtracking Leetcode: Letter Combinations of a Phone Number
13 Remove nodes from linked list #linkedlist, #presum Leetcode: Remove Zero Sum Consecutive Nodes from Linked List
14 Check whether a linked list has a loop    
15 Two pointers #twosum, #twopointer Leetcode: Two Sum
16 Buy stock for maximum profit list #array, #greedy, #buystock Leetcode: Best Time to Buy and Sell Stock
17 Prefix search from a list of strings #trie Leetcode: Longest Word in Dictionary
18 Factor Combinations #combination, #backtracking Leetcode: Factor Combinations
19 Permutation without duplicates #permutation, #backtracking Leetcode: Palindrome Permutation II
20 Int to string or string to int #bitmanipulation  
21 Convert a number into negative base representation #bitmanipulation, #baseconversion Leetcode: Convert to Base -2
22 Network connectivity #unionfind Leetcode: Friend Circles
23 Build relationship among different sets #unionfind Leetcode: Accounts Merge
24 Knapsack problem to maximize benefits #knapsack Leetcode: Coin Change
25 Find the next greater value #monotone Leetcode: Daily Temperatures
26 Meeting conflict #interval Leetcode: Meeting Rooms, Leetcode: Course Schedule
27 Minimum conference rooms #interval, #overlappinginterval Leetcode: Meeting Rooms II
28 Quick slow pointers #twopointer LintCode: Middle of Linked List
29 Longest Repeating Character with at most K changes #slidingwindow Leetcode: Longest Repeating Character Replacement
30 Count out of boundary paths in a 2D matrix #bfs, #outofboundarypath Leetcode: Out of Boundary Paths
31 Prefix and Suffix Search #trie Leetcode: Prefix and Suffix Search
32 Remove duplicate letters #greedy, #string, #stack Leetcode: Remove Duplicate Letters
33 Beautiful array #divideconquer Leetcode: Beautiful Array
34 Whether 132 pattern exists in array #stack Leetcode: 132 Pattern
35 Detect conflicts of intervals #interval Leetcode: Non-overlapping Intervals
36 Segment tree: solves range query problems quickly #segmenttree Leetcode: Range Sum Query – Mutable
37     Travelling salesman problem
38     Leetcode: Remove Duplicates from Sorted Array II
39     Leetcode: Min Stack
40   #minmax, #dynamicprogramming Leetcode: Predict the Winner, Leetcode: Stone Game
41 Topological Sort    
42      
43      
44      

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


Leave a Reply

Your email address will not be published. Required fields are marked *