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.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

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

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.14 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 Get all possibilities of subsets #subset, #backtracking Leetcode: Subsets II, Leetcode: Subsets
10 Choose k numbers from a list #combination, #backtracking Leetcode: Combination Sum II
11 Combination from multiple segments #combination, #backtracking Leetcode: Letter Combinations of a Phone Number
12 Remove nodes from linked list #linkedlist, #presum Leetcode: Remove Zero Sum Consecutive Nodes from Linked List
13 Check whether a linked list has a loop    
14 Two pointers #twosum, #twopointer Leetcode: Two Sum
15 Buy stock for maximum profit list #array, #greedy, #buystock Leetcode: Best Time to Buy and Sell Stock
16 Prefix search from a list of strings #trie Leetcode: Longest Word in Dictionary
17 Factor Combinations #combination, #backtracking Leetcode: Factor Combinations
18 Permutation without duplicates #permutation, #backtracking Leetcode: Palindrome Permutation II
19 Int to string or string to int #bitmanipulation  
20 Convert a number into negative base representation #bitmanipulation, #baseconversion Leetcode: Convert to Base -2
21 Network connectivity #unionfind Leetcode: Friend Circles
22 Build relationship among different sets #unionfind Leetcode: Accounts Merge
23 Find the next greater value #monotone Leetcode: Daily Temperatures
24 Meeting conflict #interval Leetcode: Meeting Rooms, Leetcode: Course Schedule
25 Minimum conference rooms #interval, #meetingconflict Leetcode: Meeting Rooms II
26 Quick slow pointers #twopointer LintCode: Middle of Linked List
27 Longest Repeating Character with at most K changes #slidingwindow Leetcode: Longest Repeating Character Replacement
28 Prefix and Suffix Search #trie Leetcode: Prefix and Suffix Search
29 Remove duplicate letters #greedy, #string, #stack Leetcode: Remove Duplicate Letters
30 Beautiful array #divideconquer Leetcode: Beautiful Array
31 Whether 132 pattern exists in array #stack Leetcode: 132 Pattern
32 Detect conflicts of intervals #interval Leetcode: Non-overlapping Intervals
33 Segment tree: solves range query problems quickly #segmenttree Leetcode: Range Sum Query – Mutable
34 Find best meeting points for a list of nodes #meetingpoint Leetcode: Best Meeting Point
35 Find the size of longest wiggle subsequence #subsequence, #wiggle Leetcode: Wiggle Subsequence
36 Sequence reconstruction #topologicalsort Leetcode: Sequence Reconstruction
37 Construct Binary Tree from String #stack Construct Binary Tree from String
38 Use more space to save time #stack Leetcode: Min Stack
39 Min max game problems #minmax, #dynamicprogramming Leetcode: Predict the Winner, Leetcode: Stone Game
40 Shortest Subarray with Sum at Least K #monotone Leetcode: Shortest Subarray with Sum at Least K
41 Wiggle sort   Leetcode: Wiggle Sort II
42     Leetcode: Remove Duplicates from Sorted Array II
43     Travelling salesman problem
44 Array compressed storage #oodesign, #game Leetcode: Design Tic-Tac-Toe

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  

Leave a Reply

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