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

1.3 Typical Followup

Num Name Summary
1 From 1-D array to 2-D matrix LeetCode: Number of Submatrices That Sum to Target
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 Instead of a fixed list, it’s an ongoing data stream Leetcode: Flatten 2D Vector

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 Graph trasversal from boarders 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 shortest distance from point1 to point2 LeetCode: Word Ladder, LeetCode: Sliding Puzzle
17 Find shortest distance in a weighted graph LeetCode: Find the City With the Smallest Number of Neighbors
18 Find all minimum paths from point1 to point2 LeetCode: Word Ladder II
19 All Paths from Source Lead to Destination LeetCode: All Paths from Source Lead to Destination
20 Node connectivity problem for a sparse 2D matrix LeetCode: Escape a Large Maze
21 Bricks Falling When Hit LeetCode: Bricks Falling When Hit
22 Bridges in a connected graph – Tarjan’s algorithm LeetCode: Critical Connections in a Network
23 Valid & Invalid moves LeetCode: Alphabet Board Path
24 Move in different directions: 4 directions, 8 directions LeetCode: Queens That Can Attack the King
25 String Transforms Into Another String LeetCode: String Transforms Into Another String
26 Candidates are (i, j, r), instead of (i, j) LeetCode: Shortest Path in a Grid with Obstacles Elimination
27 Clone Graph Leetcode: Clone Graph
28 Array problem with hidden graph LeetCode: Number of Squareful Arrays
29 Is Graph Bipartite LeetCode: Is Graph Bipartite
30 Search an infinite graph LeetCode: Escape a Large Maze
leetcode

1.5 Top 25 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 Find the first and last target LeetCode: Find First and Last Position of Element in Sorted Array
5 Search Insert Position LeetCode: Search Insert Position, LeetCode: Time Based Key-Value Store
6 Mountain Array LeetCode: Peak Index in a Mountain Array
7 Missing Element in Sorted Array LeetCode: Missing Element in Sorted Array
8 Find smallest letter greater than target LeetCode: Find Smallest Letter Greater Than Target
9 Random Point in Non-overlapping Rectangles LeetCode: Random Point in Non-overlapping Rectangles
10 Binary search on monotonic function LeetCode: Sqrt(x), LeetCode: Capacity To Ship Packages Within D Days
11 Place k elements to minimize max distance LeetCode: Minimize Max Distance to Gas Station
12 Decide a number LeetCode: Split Array Largest Sum
13 Kth Smallest Number in Multiplication Table LeetCode: Kth Smallest Number in Multiplication Table
14 Search for a Range Leecode: Search for a Range
15 Dynamic programming with binary search LeetCode: Maximum Profit in Job Scheduling
16 Montone stack with binary search LeetCode: Maximum Width Ramp
17 Find Right Interval Leecode: Find Right Interval
18 Patient sort LeetCode: Longest Increasing Subsequence
19 Find Minimum in Rotated Sorted Array LeetCode: Find Minimum in Rotated Sorted Array
20 Find Minimum in Rotated Sorted Array II LeetCode: Find Minimum in Rotated Sorted Array II
21 Maximum Profit in Job Scheduling Leetcode: Maximum Profit in Job Scheduling
22 Tweet Counts Per Frequency LeetCode: Tweet Counts Per Frequency
23 Median of Two Sorted Arrays Leetcode: Median of Two Sorted Arrays

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 Swap odd with even nodes Leetcode: Swap Nodes in Pairs
4 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 Use monotone stack to find next bigger value LeetCode: Next Greater Element I
2 Monotone stack for consecutive subarrays LeetCode: Online Stock Span, LeetCode: Sum of Subarray Minimums
3 Shortest Subarray with Sum at Least K LeetCode: Shortest Subarray with Sum at Least K
4 Monotone queue LeetCode: Constrained Subset Sum, LeetCode: Sliding Window Maximum

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 Sliding window with lazy removal Leetcode: Sliding Window Median
10 Get all possibilities of subsets LeetCode: Subsets II, LeetCode: Subsets
11 Choose k numbers from a list LeetCode: Combination Sum II
12 Combination from multiple segments LeetCode: Letter Combinations of a Phone Number
13 Remove nodes from linked list LeetCode: Remove Zero Sum Consecutive Nodes from Linked List
14 Two pointers LeetCode: Two Sum
15 Buy stock for maximum profit list LeetCode: Best Time to Buy and Sell Stock
16 Prefix search from a list of strings LeetCode: Longest Word in Dictionary
17 Factor Combinations LeetCode: Factor Combinations
18 Permutation without duplicates LeetCode: Palindrome Permutation II
19 Convert a number into negative base representation LeetCode: Convert to Base -2
20 Network connectivity LeetCode: Friend Circles
21 Build relationship among different sets LeetCode: Accounts Merge
22 Find the next greater value LeetCode: Daily Temperatures
23 Meeting conflict LeetCode: Meeting Rooms, LeetCode: Course Schedule
24 Minimum conference rooms LeetCode: Meeting Rooms II
25 Quick slow pointers LintCode: Middle of Linked List
26 Longest Repeating Character with at most K changes LeetCode: Longest Repeating Character Replacement
27 Prefix and Suffix Search LeetCode: Prefix and Suffix Search
28 Remove duplicate letters LeetCode: Remove Duplicate Letters
29 Beautiful array LeetCode: Beautiful Array
30 Whether 132 pattern exists in array LeetCode: 132 Pattern
31 Detect conflicts of intervals LeetCode: Non-overlapping Intervals
32 Segment tree: solves range query problems quickly LeetCode: Range Sum Query – Mutable
33 Find best meeting points for a list of nodes LeetCode: Best Meeting Point
34 Find the size of longest wiggle subsequence LeetCode: Wiggle Subsequence
35 Sequence reconstruction LeetCode: Sequence Reconstruction
36 Construct Binary Tree from String Construct Binary Tree from String
37 Use more space to save time LeetCode: Min Stack
38 Min max game problems LeetCode: Predict the Winner, LeetCode: Stone Game
39 Shortest Subarray with Sum at Least K LeetCode: Shortest Subarray with Sum at Least K
40 Wiggle sort LeetCode: Wiggle Sort II
41 Array compressed storage LeetCode: Design Tic-Tac-Toe
42 Dead lock: the Dining Philosophers LeetCode: The Dining Philosophers
43 Maintain the order LeetCode: Building H2O
44 Int to string or string to int  
45 Expression Add Operators LeetCode: Expression Add Operators
46 Merge k Sorted Lists LeetCode: Merge k Sorted Lists
47 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  
34 Reduce search space Leetcode: Bulb Switcher II


Leave a Reply

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