- PDF Link: cheatsheet-leetcode-A4.pdf, Category: interview
- Blog URL: https://cheatsheet.dennyzhang.com/cheatsheet-leetcode-A4
- Related posts: CheatSheet: System Design For Job Interview, #denny-cheatsheets
File me Issues or star this repo.
Name | Summary |
---|---|
Cheatsheet | CheatSheet: Leetcode For Code Interview, CheatSheet: Common Code Problems & Follow-ups |
Cheatsheet | CheatSheet: System Design For Job Interview, CheatSheet: SRE/DevOps/Sysadmin |
Cheatsheet | CheatSheet: Behavior Questions For Coder Interview |
Leetcode summary | Link: Top Google Questions, Link: Top 100 Liked Questions, Link: Top Interview Questions |
Leetcode summary | GitHub: kdn251/interviews, Github: Algorithms-and-Coding-Interviews |
YouTube | How to: Work at Google - Example Coding/Engineering Interview, lee 215, Aoxiang Cui, happygirlzt |
Online test websites | hihocoder.com, codeforces.com, spoj.com, Google - codejam, hackerrank.com |
Online test websites | hackerrank - hard, poj.org, acm.hdu.edu.cn, acm.zju.edu.cn, acm.timus.ru, uva.onlinejudge.org |
visualgo | visualizing data structures and algorithms through animation |
Reference | geeksforgeeks.org, Youtube: Abdul Bari - Algorithm |
Reference | COS 423 Theory of Algorithms, 6.006: Introduction to Algorithms - MIT |
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 |
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 |
Num | Problem | Summary |
---|---|---|
1 | Binary Tree Level Order Traversal | LeetCode: Binary Tree Right Side View |
2 | Tree Traversal: Binary Tree Vertical Order Traversal | LeetCode: Binary Tree Vertical Order Traversal |
3 | Tree Traversal: Find Leaves of Binary Tree | Leetcode: Find Leaves of Binary Tree |
4 | Get binary tree height, width | LeetCode: Balanced Binary Tree |
5 | LCA - Lowest Common Ancestor of a binary Tree | LeetCode: Lowest Common Ancestor of a Binary Tree |
6 | Validate Binary Search Tree | LeetCode: Validate Binary Search Tree |
7 | Construct binary tree | LeetCode: Construct Binary Tree from Preorder and Postorder Traversal |
8 | Distribute Coins in Binary Tree | LeetCode: Distribute Coins in Binary Tree |
9 | Binary Tree Vertical Order Traversal | LeetCode: Binary Tree Vertical Order Traversal |
10 | Verify Preorder Sequence in Binary Search Tree | LeetCode: Verify Preorder Sequence in Binary Search Tree |
11 | Recursive + Greedy | LeetCode: Binary Tree Coloring Game |
12 | Binary tree + greedy | LeetCode: Binary Tree Cameras |
13 | Revert binary tree between left and right | |
14 | binary tree serialization and deserialization | |
15 | Morris tree trasversal | |
16 | Find the next node of binary search tree | |
17 | Count Complete Tree Nodes | LeetCode: Count Complete Tree Nodes |
18 | Binary Tree Upside Down | Leetcode: Binary Tree Upside Down |
19 | Closest Binary Search Tree Value II | Leetcode: Closest Binary Search Tree Value II |
Num | Problem | Summary |
---|---|---|
1 | Edit distance of two strings | LeetCode: Edit Distance |
2 | Remove duplicate letters | Remove Duplicate Letters |
3 | Word ladder | LeetCode: Word Ladder |
4 | lrs - Longest repeating substring | LeetCode: Longest Repeating Substring |
5 | Remove Comments | LeetCode: Remove Comments |
6 | Split Concatenated Strings | LeetCode: Split Concatenated Strings |
7 | Vowel Spellchecker | LeetCode: Vowel Spellchecker |
8 | Lexicographically minimal string rotation | LeetCode: Last Substring in Lexicographical Order |
9 | String Transforms Into Another String | LeetCode: String Transforms Into Another String |
10 | Find the Closest Palindrome | LeetCode: Find the Closest Palindrome |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
Num | Name | Summary |
---|---|---|
1 | Trial and error | |
2 | Divide and Conquer | |
3 | Start with naive algorithm, then identify useless steps |
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 |
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 |
License: Code is licensed under MIT License.
https://en.wikipedia.org/wiki/Data_structure
https://www.cs.princeton.edu/~rs/AlgsDS07/
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/