Using CheatSheets To Apply Best Practices

Cheatsheet: Leetcode Common Templates & Common Code Problems

Cheatsheet: Leetcode Common Templates & Common Code Problems

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

1.4 Top 15 Dynamic Programming Problems

Num Problem Time Complexity Category/Tag Summary
1 Maximum subarray problemKadane’s algorithm O(n) #maxsubarraysum, #dynamicprogramming Leetcode: Maximum Subarray
2 LIS – Longest increasing subsequence O(n) #lis, #string, #dynamicprogramming Leetcode: Longest Increasing Subsequence
3 LCS – Longest Common Subsequence O(n*m) #lcs, #editdistance, #dynamicprogramming Leetcode: Longest Common Subsequence
4 LPS – Longest Palindromic Subsequence O(n) #palindrome, #dynamicprogramming Leetcode: Longest Palindromic Subsequence
5 Longest Palindromic Substring O(n2)/O(n) #palindrome,#dynamicprogramming Leetcode: Longest Palindromic Substring
6 Edit distance of two strings O(n2) #editdistance, #dynamicprogramming Leetcode: Edit Distance
7 Count of distinct subsequence O(n) #countdistinctmoves, #hashmap Leetcode: Distinct Subsequences II
8 Maximum profits with certain costs O(n2) #maxprofitwithcost, #dynamicprogramming Leetcode: 4 Keys Keyboard
9 Get two subset with the same sum O(n*s) #knapsack, #dynamicprogramming Leetcode: Tallest Billboard
10 Count out of boundary paths in a 2D matrix O(n*m*N) #countdistinctmoves, #bfs Leetcode: Out of Boundary Paths
11 Regular Expression Matching O(n*m) #editdistance, #dynamicprogramming Leetcode: Regular Expression Matching
12 Wildcard Matching O(n*m) #editdistance, #dynamicprogramming Leetcode: Wildcard Matching
13 Multiple choices for each step O(n*m) #dynamicprogramming Leetcode: Filling Bookcase Shelves
14 Minimum-weight triangulation O(n*n*n) #dynamicprogramming Leetcode: Minimum Score Triangulation of Polygon

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

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.11 Top 50 General Problems

Num Problem Category/Tag Example
1 Longest substring with at most K distinct characters #slidingwindow, #atmostkdistinct Leetcode: Longest Substring with At Most K Distinct Characters
2 Longest subarray with maximum K 0s #slidingwindow Leetcode: Max Consecutive Ones III
3 Seperate a list into several groups #groupelements, #twopointer Leetcode: Summary Ranges
4 Split string #string Leetcode: License Key Formatting
5 TopK problem #heap, #topk Leetcode: Top K Frequent Elements, Leetcode: Find K Pairs with Smallest Sums
6 Longest Palindromic Subsequence #dynamicprogramming Leetcode: Longest Palindromic Subsequence
7 Sort one array based on another array #sortbyfunction Leetcode: Relative Sort Array
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, #meetingconflict 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 Prefix and Suffix Search #trie Leetcode: Prefix and Suffix Search
31 Remove duplicate letters #greedy, #string, #stack Leetcode: Remove Duplicate Letters
32 Beautiful array #divideconquer Leetcode: Beautiful Array
33 Whether 132 pattern exists in array #stack Leetcode: 132 Pattern
34 Detect conflicts of intervals #interval Leetcode: Non-overlapping Intervals
35 Segment tree: solves range query problems quickly #segmenttree Leetcode: Range Sum Query – Mutable
36 Find best meeting points for a list of nodes #meetingpoint Leetcode: Best Meeting Point
37 Find the size of longest wiggle subsequence #subsequence, #wiggle Leetcode: Wiggle Subsequence
38 Sequence reconstruction #topologicalsort Leetcode: Sequence Reconstruction
39 Construct Binary Tree from String #stack Construct Binary Tree from String
40 Use more space to save time #stack Leetcode: Min Stack
41 Min max game problems #minmax, #dynamicprogramming Leetcode: Predict the Winner, Leetcode: Stone Game
42 Shortest Subarray with Sum at Least K #monotone Leetcode: Shortest Subarray with Sum at Least K
43 Wiggle sort   Leetcode: Wiggle Sort II
44     Leetcode: Remove Duplicates from Sorted Array II
45     Travelling salesman problem
46 Array compressed storage #oodesign, #game Leetcode: Design Tic-Tac-Toe

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  


Leave a Reply

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