Using CheatSheets To Apply Best Practices

Cheatsheet: Leetcode Common Templates & Common Code Problems

Cheatsheet: Leetcode Common Templates & Common Code Problems

1.2 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 Find shortest distance for two nodes in an undirected graph  
4 Cycle detection in a directed graph Leetcode: Redundant Connection II
5 Detect all cycles in a directed graph Leetcode: Find Eventual Safe States
6 Whether a graph is a tree Leetcode: Graph Valid Tree
7 Minimum Spanning Tree(MST) of a weighted graph – Kruskal’s algorithm Leetcode: Connecting Cities With Minimum Cost
8 Find shortest paths in a weighted graph – Floyd-Warshall algorithm  
9 Shortest path for two nodes in a weighted graph – Dijkstra’s algorithm Leetcode: Connecting Cities With Minimum Cost
10 Update a specific region Leetcode: Flood Fill
11 Update regions for a given rule Leetcode: Surrounded Regions
12 Number of Distinct Islands Leetcode: Number of Distinct Islands
13 Mark levels Leetcode: 01 Matrix
14 Diameter of a tree in graph theory Leetcode: Tree Diameter
15 Duplicate edges Leetcode: Reconstruct Itinerary
16 Find a certain node in a graph Leetcode: Find the Celebrity
17 Coloring graph Leetcode: Minesweeper
18 Find a certain path from source to destination in a graph Leetcode: Path With Maximum Minimum Value
19 Find the minimum steps from point1 to point2 Leetcode: Word Ladder, Leetcode: Sliding Puzzle
20 Find all minimum paths from point1 to point2 Leetcode: Word Ladder II
21 All Paths from Source Lead to Destination Leetcode: All Paths from Source Lead to Destination
22 Node connectivity problem for a sparse 2D matrix Leetcode: Escape a Large Maze
23 Bricks Falling When Hit Leetcode: Bricks Falling When Hit
24 Bridges in a connected graph – Tarjan’s algorithm Leetcode: Critical Connections in a Network
25 Valid & Invalid moves Leetcode: Alphabet Board Path
26 Move in different directions: 4 directions, 8 directions Leetcode: Queens That Can Attack the King
27 String Transforms Into Another String Leetcode: String Transforms Into Another String

https://code.dennyzhang.com

denny_leetcode.png

1.3 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.4 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.5 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 Revert binary tree between left and right  
8 binary tree + greedy Leetcode: Binary Tree Cameras
9 binary tree serialization and deserialization  
10 Morris tree trasversal  
11 Leetcode: Binary Tree Vertical Order Traversal Leetcode: Binary Tree Vertical Order Traversal

1.6 Top 10 String Problems

1.7 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.8 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.9 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.10 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 Check if two line segments intersect  
6 Rotate Array by k steps Leetcode: Rotate Array
7 Mapping data range of getRand algorithm Leetcode: Implement Rand10() Using Rand7()
8 Deal with float Leetcode: Minimize Max Distance to Gas Station
9 Sum of Subsequence Widths Leetcode: Sum of Subsequence Widths
10 Remove 9 Leetcode: Remove 9
11 Fraction to Recurring Decimal Leetcode: Fraction to Recurring Decimal

1.11 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.12 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.13 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.14 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.15 Top 5 Backtracking Problems

Num Problem Summary
1 Subsets II Leetcode: Subsets II
2 Expression Add Operators Leetcode: Expression Add Operators

1.17 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

1.18 Basic Thinking Methodologies

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

1.19 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.20 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 Hide details which are irrelevant  
31 One pass instead of two pass  
32 Avoid unnecessary precheck  

1.21 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.22 More Data Structure

Name Summary
Tree map  
Inverted Index  


Leave a Reply

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