Using CheatSheets To Apply Best Practices

Cheatsheet: LeetCode Common Templates & Common Code Problems

Cheatsheet: LeetCode Common Templates & Common Code Problems

1.2 Top 25 Code Templates

Num Category/Tag Example
1 #bfs Leetcode: Max Area of Island
2 #dfs LeetCode: Surrounded Regions
3 #binarysearch LeetCode: Search Insert Position
4 #interval, #mergelist LeetCode: Interval List Intersections, Leetcode: Merge Intervals
5 #twopointer LeetCode: Reverse Words in a String II, LeetCode: Two Sum
6 #twopointer, #mergetwolist LeetCode: Merge Sorted Array, Leetcode: Container With Most Water
7 #backtracking, #subset LeetCode: Subsets II
8 #linkedlist, #presum LeetCode: Remove Zero Sum Consecutive Nodes from Linked List
9 #unionfind LeetCode: Accounts Merge
10 #trie LeetCode: Longest Word in Dictionary
11 #stack LeetCode: Valid Parentheses
12 #stack LeetCode: Reverse Substrings Between Each Pair of Parentheses
13 #heap LeetCode: Top K Frequent Elements
14 #baseconversion LeetCode: Base 7, LeetCode: Convert to Base -2
15 #interval LeetCode: Meeting Rooms II, LeetCode: My Calendar I
16 #monotone LeetCode: Daily Temperatures
17 #knapsack LeetCode: Coin Change
18 #sortbyfunction LeetCode: Relative Sort Array
19 #slidingwindow LeetCode: Longest Substring Without Repeating Characters
20 #editdistance, #dynamicprogramming LeetCode: Longest Common Subsequence
21 #topologicalsort LeetCode: Course Schedule
22 #bfs, bidirectional bfs LeetCode: Word Ladder
23 #monotonicfunc, #binarysearch LeetCode: Kth Smallest Number in Multiplication Table
24 #divideconquer, #recursive Leetcode: Count of Smaller Numbers After Self
25 #linesweep Leetcode: Employee Free Time, Leetcode: The Skyline Problem

CheatSheet: Leetcode Common Templates & Common Code Problems

1.3 Typical Followup

Num Name Summary
1 From 1-D array to 2-D matrix  
2 Instead of O(n) space, use O(1) space LeetCode: Find Mode in Binary Search Tree
3 How to do it with multi-threading LeetCode: Web Crawler Multithreaded
4 Data values have different ranges LeetCode: Find Median from Data Stream
5 Solve with iterator without pre-loading Leetcode: Flatten 2D Vector
6 Instead of a fixed list, it’s an ongoing data stream  

1.4 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 Cycle detection in a directed graph LeetCode: Redundant Connection II
4 Detect all cycles in a directed graph LeetCode: Find Eventual Safe States
5 Whether a graph is a tree LeetCode: Graph Valid Tree
6 Update a specific region LeetCode: Flood Fill
7 Update regions for a given rule LeetCode: Surrounded Regions
8 Number of Distinct Islands LeetCode: Number of Distinct Islands
9 Mark levels LeetCode: 01 Matrix
10 Diameter of a tree in graph theory LeetCode: Tree Diameter
11 Duplicate edges LeetCode: Reconstruct Itinerary
12 Find a certain node in a graph LeetCode: Find the Celebrity
13 Graph with next steps by a trie Leetcode: Word Search II
14 Coloring graph LeetCode: Minesweeper
15 Find a certain path from source to destination in a graph LeetCode: Path With Maximum Minimum Value
16 Find the minimum steps from point1 to point2 LeetCode: Word Ladder, LeetCode: Sliding Puzzle
17 Find all minimum paths from point1 to point2 LeetCode: Word Ladder II
18 All Paths from Source Lead to Destination LeetCode: All Paths from Source Lead to Destination
19 Node connectivity problem for a sparse 2D matrix LeetCode: Escape a Large Maze
20 Bricks Falling When Hit LeetCode: Bricks Falling When Hit
21 Bridges in a connected graph – Tarjan’s algorithm LeetCode: Critical Connections in a Network
22 Valid & Invalid moves LeetCode: Alphabet Board Path
23 Move in different directions: 4 directions, 8 directions LeetCode: Queens That Can Attack the King
24 String Transforms Into Another String LeetCode: String Transforms Into Another String
25 Candidates are (i, j, r), instead of (i, j) LeetCode: Shortest Path in a Grid with Obstacles Elimination
26 Clone Graph Leetcode: Clone Graph
27 Array problem with hidden graph LeetCode: Number of Squareful Arrays
28 Find shortest paths in a weighted graph LeetCode: Find the City With the Smallest Number of Neighbors
29 Graph trasversal from boarders Leetcode: Surrounded Regions
30 Is Graph Bipartite LeetCode: Is Graph Bipartite
leetcode

1.5 Top 20 Binarysearch Problems

Num Problem Summary
1 Find whether target in the range LeetCode: Guess Number Higher or Lower
2 Find the first target with duplicates LeetCode: First Bad Version
3 Find the last target with duplicates LeetCode: Longest Repeating Substring
4 Search Insert Position LeetCode: Search Insert Position, LeetCode: Time Based Key-Value Store
5 Missing Element in Sorted Array LeetCode: Missing Element in Sorted Array
6 Find smallest letter greater than target LeetCode: Find Smallest Letter Greater Than Target
7 Random Point in Non-overlapping Rectangles LeetCode: Random Point in Non-overlapping Rectangles
8 Binary search on monotonic function LeetCode: Sqrt(x), LeetCode: Capacity To Ship Packages Within D Days
9 Place k elements to minimize max distance LeetCode: Minimize Max Distance to Gas Station
10 Kth Smallest Number in Multiplication Table LeetCode: Kth Smallest Number in Multiplication Table
11 Search for a Range Leecode: Search for a Range
12 Mountain Array LeetCode: Peak Index in a Mountain Array
13 Dynamic programming with binary search LeetCode: Maximum Profit in Job Scheduling
14 Montone stack with binary search LeetCode: Maximum Width Ramp
15 Find Right Interval Leecode: Find Right Interval
16 Patient sort LeetCode: Longest Increasing Subsequence
17 Find Minimum in Rotated Sorted Array LeetCode: Find Minimum in Rotated Sorted Array
18 Find Minimum in Rotated Sorted Array II LeetCode: Find Minimum in Rotated Sorted Array II

1.6 Top 25 Dynamic Programming Problems

Num Problem Time Complexity Summary
1 Maximum subarray problemKadane’s algorithm O(n) LeetCode: Maximum Subarray
2 LIS – Longest increasing subsequence O(n) LeetCode: Longest Increasing Subsequence
3 LCS – Longest Common Subsequence O(n*m) LeetCode: Longest Common Subsequence
4 LPS – Longest Palindromic Subsequence O(n) LeetCode: Longest Palindromic Subsequence
5 Longest Palindromic Substring O(n2) LeetCode: Longest Palindromic Substring
6 Edit distance of two strings O(n2) LeetCode: Edit Distance
7 Maximum profits with certain costs O(n2) LeetCode: 4 Keys Keyboard
8 Count of distinct subsequence O(n) LeetCode: Distinct Subsequences II
9 Count out of boundary paths in a 2D matrix O(n*m*N) LeetCode: Out of Boundary Paths
10 Regular Expression Matching O(n*m) LeetCode: Regular Expression Matching
11 Wildcard Matching O(n*m) LeetCode: Wildcard Matching
12 Multiple choices for each step O(n*m) LeetCode: Filling Bookcase Shelves
13 Knapsack: put array to bag A, B or discard it O(n*s) LeetCode: Tallest Billboard
14 Knapsack problem to maximize benefits O(n*s) LeetCode: Coin Change
15 Minimum Cost to Merge Stones O(n3) LeetCode: Minimum Cost to Merge Stones
16 DP over interval: Minimum-weight triangulation O(n3) LeetCode: Minimum Score Triangulation of Polygon
17 Burst Balloons O(n3) LeetCode: Burst Balloons
18 Remove Boxes O(n4) LeetCode: Remove Boxes
19 Largest Sum of Averages O(k*n*n) LeetCode: Largest Sum of Averages
20 Uncrossed Lines O(n*m) LeetCode: Uncrossed Lines
21 Binary Trees With Factors O(n2) LeetCode: Binary Trees With Factors

1.7 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.8 Top 10 String Problems

1.9 Top 5 Stack Problems

Num Problem Summary
1 Recursive deletion during pushing process LeetCode: Verify Preorder Serialization of a Binary Tree
2 Examine whether the input string is valid LeetCode: Asteroid Collision
3 When pushing to stack, whether delayed push LeetCode: Decode String

1.10 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.11 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.12 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.13 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.14 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.15 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.16 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.17 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.18 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.19 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.21 Top 50 General Problems

Num Problem Example
1 Longest substring with at most K distinct characters LeetCode: Longest Substring with At Most K Distinct Characters
2 Longest subarray with maximum K 0s LeetCode: Max Consecutive Ones III
3 Seperate a list into several groups LeetCode: Summary Ranges
4 Split string LeetCode: License Key Formatting
5 TopK problem LeetCode: Top K Frequent Elements, LeetCode: Find K Pairs with Smallest Sums
6 Longest Palindromic Subsequence LeetCode: Longest Palindromic Subsequence
7 Sort one array based on another array LeetCode: Relative Sort Array
8 Range update with lazy propagation LeetCode: Corporate Flight Bookings
9 Get all possibilities of subsets LeetCode: Subsets II, LeetCode: Subsets
10 Choose k numbers from a list LeetCode: Combination Sum II
11 Combination from multiple segments LeetCode: Letter Combinations of a Phone Number
12 Remove nodes from linked list LeetCode: Remove Zero Sum Consecutive Nodes from Linked List
13 Two pointers LeetCode: Two Sum
14 Buy stock for maximum profit list LeetCode: Best Time to Buy and Sell Stock
15 Prefix search from a list of strings LeetCode: Longest Word in Dictionary
16 Factor Combinations LeetCode: Factor Combinations
17 Permutation without duplicates LeetCode: Palindrome Permutation II
18 Convert a number into negative base representation LeetCode: Convert to Base -2
19 Network connectivity LeetCode: Friend Circles
20 Build relationship among different sets LeetCode: Accounts Merge
21 Find the next greater value LeetCode: Daily Temperatures
22 Meeting conflict LeetCode: Meeting Rooms, LeetCode: Course Schedule
23 Minimum conference rooms LeetCode: Meeting Rooms II
24 Quick slow pointers LintCode: Middle of Linked List
25 Longest Repeating Character with at most K changes LeetCode: Longest Repeating Character Replacement
26 Prefix and Suffix Search LeetCode: Prefix and Suffix Search
27 Remove duplicate letters LeetCode: Remove Duplicate Letters
28 Beautiful array LeetCode: Beautiful Array
29 Whether 132 pattern exists in array LeetCode: 132 Pattern
30 Detect conflicts of intervals LeetCode: Non-overlapping Intervals
31 Segment tree: solves range query problems quickly LeetCode: Range Sum Query – Mutable
32 Find best meeting points for a list of nodes LeetCode: Best Meeting Point
33 Find the size of longest wiggle subsequence LeetCode: Wiggle Subsequence
34 Sequence reconstruction LeetCode: Sequence Reconstruction
35 Construct Binary Tree from String Construct Binary Tree from String
36 Use more space to save time LeetCode: Min Stack
37 Min max game problems LeetCode: Predict the Winner, LeetCode: Stone Game
38 Shortest Subarray with Sum at Least K LeetCode: Shortest Subarray with Sum at Least K
39 Wiggle sort LeetCode: Wiggle Sort II
40 Array compressed storage LeetCode: Design Tic-Tac-Toe
41 Dead lock: the Dining Philosophers LeetCode: The Dining Philosophers
42 Maintain the order LeetCode: Building H2O
43 Int to string or string to int  
44 Expression Add Operators LeetCode: Expression Add Operators
45 Merge k Sorted Lists LeetCode: Merge k Sorted Lists
46 Trapping Rain Water LeetCode: Trapping Rain Water

1.22 Basic Thinking Methodologies

Num Name Summary
1 Trial and error  
2 Divide and Conquer  
3 Start with naive algorithm, then identify useless steps  

1.23 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.24 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 When count sort, use one array instead of two LeetCode: Minimum Number of Steps to Make Two Strings Anagram
31 Hide details which are irrelevant  
32 One pass instead of two pass  
33 Avoid unnecessary precheck  


Leave a Reply

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