Array
| # |
Title |
Time |
Space |
Remark |
| Leetcode 27 |
Remove Element |
O(n) |
O(1) |
Two Pointer |
| Leetcode 26 |
Remove Duplicates from Sorted Array |
O(n) |
O(1) |
Two Pointer |
| Leetcode 80 |
Remove Duplicates from Sorted Array II |
O(n) |
O(1) |
Two Pointer |
| Leetcode 277 |
Find the Celebrity |
O(n) |
O(1) |
|
| Leetcode 189 |
Rotate Array |
O(n) |
O(1) |
|
| Leetcode 41 |
First Missing Positive |
O(n |
O(1) |
Bucket Sort |
| Leetcode 299 |
Bulls and Cows |
O(n) |
O(n) |
|
| Leetcode 134 |
Gas Station |
O(n) |
O(1) |
|
| Leetcode 274 |
H-Index |
O(n) |
O(n) |
|
| Leetcode 275 |
H-Index II |
O(logn) |
O(1) |
Binary Search |
| Leetcode 244 |
Shortest Word Distance II |
O(n^2) |
O(n) |
Hashmap |
| Leetcode 245 |
Shortest Word Distance III |
O(n^2) |
O(n) |
|
| Leetcode 217 |
Contains Duplicate |
O(n) |
O(n) |
|
| Leetcode 219 |
Contains Duplicate II |
O(n) |
O(n) |
|
| Leetcode 220 |
Contains Duplicate III |
O(n^2 |
O(1) |
|
| Leetcode 55 |
Jump Game |
O(n) |
O(1) |
Greedy |
| Leetcode 45 |
Jump Game II |
O(n) |
O(1) |
Greedy |
| Leetcode 403 |
Frog Jump |
O(n) |
O(n) |
DFS |
| Leetcode 121 |
Best Time to Buy and Sell Stock |
O(n) |
O(1) |
|
| Leetcode 122 |
Best Time to Buy and Sell Stock II |
O(n) |
O(1) |
|
| Leetcode 123 |
Best Time to Buy and Sell Stock III |
O(n) |
O(n) |
|
| Leetcode 188 |
Best Time to Buy and Sell Stock IV |
O(n*k) |
O(n*k) |
DP |
| Leetcode 309 |
Best Time to Buy and Sell Stock with Cooldown |
O(n) |
O(n) |
DP |
| Leetcode 11 |
Container With Most Water |
O(n) |
O(1) |
Two Pointer |
| Leetcode 42 |
Trapping Rain Water |
O(n) |
O(1) |
Two Pointer |
| Leetcode 334 |
Increasing Triplet Subsequence |
O(n) |
O(1) |
|
| Leetcode 128 |
Longest Consecutive Sequence |
O(n) |
O(n) |
|
| Leetcode 287 |
Find the Duplicate Number |
O(nlogn) |
O(1) |
Binary Search |
| Leetcode 289 |
Game of Life |
O(m*n) |
O(1) |
|
| Leetcode 57 |
Insert Interval |
O(n) |
O(1) |
|
| Leetcode 56 |
Merge Intervals |
O(nlogn) |
O(1) |
|
| Leetcode 986 |
Interval List Intersections |
O(m+n) |
O(1) |
|
| Leetcode 252 |
Meeting Rooms |
O(nlogn) |
O(1) |
|
| Leetcode 253 |
Meeting Rooms II |
O(nlogn) |
O(n) |
|
| Leetcode 352 |
Data Stream as Disjoint Intervals |
O(n) |
O(1) |
|
| Leetcode 239 |
Sliding Window Maximum |
O(n) |
O(n) |
|
| Leetcode 295 |
Find Median from Data Stream |
O(nlogn) |
O(n) |
|
| Leetcode 1093 |
Statistics from a Large Sample |
O(1) |
O(1) |
295 follow up |
| Leetcode 53 |
Maximum Subarray |
O(n) |
O(n) |
|
| Leetcode 325 |
Maximum Size Subarray Sum Equals k |
O(n) |
O(n) |
|
| Leetcode 209 |
Minimum Size Subarray Sum |
O(n) |
O(1) |
Two Pointer |
| Leetcode 238 |
Product of Array Except Self |
O(n) |
O(n) |
|
| Leetcode 152 |
Maximum Product Subarray |
O(n) |
O(1) |
|
| Leetcode 228 |
Summary Ranges |
O(n) |
O(1) |
|
| Leetcode 163 |
Missing Ranges |
O(n) |
O(1) |
|
| Leetcode 88 |
Merge Sorted Array |
O(n) |
O(1) |
Two Pointer |
| Leetcode 75 |
Sort Colors |
O(n) |
O(1) |
Two Pointer |
| Leetcode 283 |
Move Zeroes |
O(n) |
O(1) |
Two Pointer |
| Leetcode 376 |
Wiggle Subsequence |
O(n) |
O(1) |
|
| Leetcode 280 |
Wiggle Sort |
O(n) |
O(1) |
|
| Leetcode 324 |
Wiggle Sort II |
O(n) |
O(n) |
|
| Leetcode 560 |
Subarray Sum Equals K |
O(n) |
O(n) |
|
| Leetcode 4 |
Median of Two Sorted Arrays |
py |
O(m+n) |
|
| Leetcode 1239 |
Maximum Length of a Concatenated String with Unique Characters |
O(2^n) |
O(n) |
|
| Leetcode 135 |
Candy |
O(n) |
O(n) |
|
| Leetcode 581 |
Shortest Unsorted Continuous Subarray |
O(n) |
O(n) |
|
| Leetcode 503 |
Next Greater Element II |
O(n) |
O(n) |
|
| Leetcode 496 |
Next Greater Element I |
O(n) |
O(n) |
|
| Leetcode 525 |
Contiguous Array |
O(n) |
O(n) |
|
| Leetcode 977 |
Squares of a Sorted Array |
O(n) |
O(n) |
|
String
| # |
Title |
Time |
Space |
Remark |
| Leetcode 28 |
Implement strStr() |
O((n-l)*l) |
O(1) |
|
| Leetcode 186 |
Reverse Words in a String II |
O(n) |
O(1) |
|
| Leetcode 205 |
Isomorphic Strings |
O(n) |
O(n) |
HashMap |
| Leetcode 293 |
Flip Game |
O(n) |
O(1) |
|
| Leetcode 294 |
Flip Game II |
O(n!) |
O(n!) |
BackTracking |
| Leetcode 290 |
Word Pattern |
O(n) |
O(n) |
HashMap |
| Leetcode 242 |
Valid Anagram |
O(nlogn) |
O(1) |
|
| Leetcode 49 |
Group Anagrams |
O(n) |
O(n) |
|
| Leetcode 249 |
Group Shifted Strings |
O(n) |
O(n) |
|
| Leetcode 161 |
One Edit Distance |
O(n) |
O(1) |
|
| Leetcode 38 |
Count and Say |
O(2^n) |
O(1) |
|
| Leetcode 316 |
Remove Duplicate Letters |
O(n) |
O(1) |
|
| Leetcode 271 |
Encode and Decode Strings |
O(n) |
O(1) |
|
| Leetcode 168 |
Excel Sheet Column Title |
O(n) |
O(1) |
|
| Leetcode 171 |
Excel Sheet Column Number |
O(n) |
O(1) |
|
| Leetcode 13 |
Roman to Integer |
O(1) |
O(1) |
|
| Leetcode 12 |
Integer to Roman |
O(n) |
O(1) |
|
| Leetcode 273 |
Integer to English Words |
O(n) |
O(1) |
|
| Leetcode 157 |
Read N Characters Given Read4 |
O(n) |
O(1) |
|
| Leetcode 158 |
Read N Characters Given Read4 II - Call multiple times |
O(n) |
O(n) |
|
| Leetcode 68 |
Text Justification |
O(n) |
O(n/kπ) |
|
| Leetcode 76 |
Minimum Window Substring |
O(n) |
O(n) |
Sliding Window |
| Leetcode 3 |
Longest Substring Without Repeating Characters |
O(n) |
O(m) |
Sliding Window |
| Leetcode 340 |
Longest Substring with At Most K Distinct Characters |
O(n) |
O(k) |
Sliding Window |
| Leetcode 125 |
Valid Palindrome |
O(n) |
O(1) |
Two Pointer |
| Leetcode 680 |
Valid Palindrome II |
O(n) |
O(n) |
Two Pointer |
| Leetcode 5 |
Longest Palindromic Substring |
O(n^2) |
O(n^2) |
DP |
| Leetcode 516 |
Longest Palindromic Subsequence |
O(n^2) |
O(n^2) |
DP |
| Leetcode 214 |
Shortest Palindrome |
O(n) |
O(n) |
|
| Leetcode 336 |
Palindrome Pairs |
O(nk^2) |
O(n) |
|
| Leetcode 1246 |
Palindrome Removal |
O(n^3) |
O(n^2) |
|
| Leetcode 20 |
Valid Parentheses |
O(n) |
O(n) |
|
| Leetcode 1249 |
Minimum Remove to Make Valid Parentheses |
O(n) |
O(n) |
|
| Leetcode 22 |
Generate Parentheses |
O(4^n)? |
O(n)? |
BackTracking |
| Leetcode 32 |
Longest Valid Parentheses |
O(n) |
O(n) |
DP |
| Leetcode 241 |
Different Ways to Add Parentheses |
? |
? |
Divide&Conquer |
| Leetcode 301 |
Remove Invalid Parentheses |
O(n*2^n) |
O(2^n) |
BFS |
| Leetcode 678 |
Valid Parenthesis String |
O(3^n) |
O(n) |
BFS |
| Leetcode 115 |
Distinct Subsequences |
O(mn) |
O(mn) |
BackTracking |
| Leetcode 844 |
Backspace String Compare |
O(m+n) |
O(1) |
Two Pointer |
| Leetcode 763 |
Partition Labels |
O(n) |
O(n) |
|
| Leetcode 616 |
Add Bold Tag in String |
? |
O(n) |
|
| Leetcode 97 |
Interleaving String |
O(mn) |
O(mn) |
|
| Leetcode 767 |
Reorganize String |
O(nlogn) |
O(n) |
|
| Leetcode 438 |
Find All Anagrams in a String |
O(n) |
O(n) |
|
| Leetcode 1156 |
Swap For Longest Repeated Character Substring |
O(n) |
O(n) |
|
Math
| # |
Title |
Time |
Space |
Remark |
| Leetcode 7 |
Reverse Integer |
O(n) |
O(1) |
|
| Leetcode 66 |
Plus One |
O(n) |
O(1) |
|
| Leetcode 8 |
String to Integer (atoi) |
O(n) |
O(1) |
|
| Leetcode 67 |
Add Binary |
O(n) |
O(1) |
|
| Leetcode 445 |
Add Two Numbers II |
O(n) |
O(n) |
|
| Leetcode 43 |
Multiply Strings |
O(m*n) |
O(m+n) |
|
| Leetcode 29 |
Divide Two Integers |
O(n) |
O(1) |
|
| Leetcode 69 |
Sqrt(x) |
O(logn) |
O(1) |
Binary Search |
| Leetcode 50 |
Pow(x, n) |
O(logn) |
O(1) or O(logn) |
|
| Leetcode 367 |
Valid Perfect Square |
O(logn) |
O(1) |
Binary Search |
| Leetcode 204 |
Count Primes |
O(nloglogn) |
O(n) |
|
| Leetcode 1 |
Two Sum |
O(n) |
O(n) |
|
| Leetcode 15 |
3Sum |
O(n^2) |
O(logn)~O(n) |
|
| Leetcode 18 |
4Sum |
O(n^3) |
O(logn)~O(n) |
|
| Leetcode 231 |
Power of Two |
O(logn) |
O(1) |
|
| Leetcode 202 |
Happy Number |
O(logn) |
O(logn) |
|
| Leetcode 263 |
Ugly Number |
O(logn) |
O(1) |
|
| Leetcode 264 |
Ugly Number II |
O(n) |
O(n) |
|
| Leetcode 223 |
Rectangle Area |
O(1) |
O(1) |
|
| Leetcode 670 |
Maximum Swap |
O(n) |
O(n) |
|
Tree
| # |
Title |
Time |
Space |
Remark |
| Leetcode 100 |
Same Tree |
O(n) |
O(logn)~O(n) |
|
| Leetcode 101 |
Symmetric Tree |
O(n) |
O(n) |
|
| Leetcode 226 |
Invert Binary Tree |
O(n) |
O(n) |
|
| Leetcode 257 |
Binary Tree Paths |
O(n) |
O(n) |
|
| Leetcode 112 |
Path Sum |
O(n) |
O(n) |
|
| Leetcode 113 |
Path Sum II |
O(n) |
O(n) |
|
| Leetcode 298 |
Binary Tree Longest Consecutive Sequence |
O(n) |
O(n) |
|
| Leetcode 111 |
Minimum Depth of Binary Tree |
O(n^2) |
O(n) |
|
| Leetcode 104 |
Maximum Depth of Binary Tree |
O(n) |
O(n) |
|
| Leetcode 110 |
Balanced Binary Tree |
O(nlogn) |
O(n) |
|
| Leetcode 124 |
Binary Tree Maximum Path Sum |
O(n) |
O(logn) |
543 |
| Leetcode 337 |
House Robber III |
O(n) |
O(n) |
|
| Leetcode 98 |
Validate Binary Search Tree |
O(n) |
O(n) |
|
| Leetcode 235 |
Lowest Common Ancestor of a Binary Search Tree |
O(n) |
O(n) |
BST |
| Leetcode 236 |
Lowest Common Ancestor of a Binary Tree |
O(n) |
O(n) |
|
| Leetcode 108 |
Convert Sorted Array to Binary Search Tree |
O(n) |
O(n) |
BST |
| Leetcode 173 |
Binary Search Tree Iterator |
O(n) |
O(n) |
BST |
| Leetcode 230 |
Kth Smallest Element in a BST |
O(n) |
O(n) |
BST |
| Leetcode 297 |
Serialize and Deserialize Binary Tree |
O(n) |
O(n) |
|
| Leetcode 285 |
Inorder Successor in BST |
O(n) |
O(H) |
BST |
| Leetcode 270 |
Closest Binary Search Tree Value |
O(n) |
O(H) |
BST |
| Leetcode 116 |
Populating Ne\xt Right Pointers in Each Node |
O(n) |
O(logn) |
|
| Leetcode 117 |
Populating Next Right Pointers in Each Node II |
O(n) |
O(n) |
|
| Leetcode 314 |
Binary Tree Vertical Order Traversal |
O(nlogn) |
O(n) |
|
| Leetcode 96 |
Unique Binary Search Trees |
O(n^2) |
O(n) |
DP |
| Leetcode 105 |
Construct Binary Tree from Preorder and Inorder Traversal |
O(n) |
O(n) |
|
| Leetcode 106 |
Construct Binary Tree from Inorder and Postorder Traversal |
O(n) |
O(n) |
|
| Leetcode 889 |
Construct Binary Tree from Preorder and Postorder Traversal |
O(n^2) |
O(n) |
|
| Leetcode 1008 |
Construct Binary Search Tree from Preorder Traversal |
O(n) |
O(n) |
|
| Leetcode 199 |
Binary Tree Right Side View |
O(n) |
O(n) |
|
| Leetcode 545 |
Boundary of Binary Tree |
O(n) |
O(n) |
|
| Leetcode 366 |
Find Leaves of Binary Tree |
O(n) |
O(n) |
|
| Leetcode 863 |
All Nodes Distance K in Binary Tree |
O(n) |
O(n) |
|
| Leetcode 109 |
Convert Sorted List to Binary Search Tree |
O(nlogn) |
O(nlogn) |
|
| Leetcode 103 |
Binary Tree Zigzag Level Order Traversal |
O(n) |
O(n) |
|
| Leetcode 543 |
Diameter of Binary Tree |
O(n) |
O(logn) |
124 |
| Leetcode 428 |
Serialize and Deserialize N-ary Tree |
O(n) |
O(n) |
|
| Leetcode 987 |
Vertical Order Traversal of a Binary Tree |
O(n) |
O(n) |
|
| Leetcode 938 |
Range Sum of BST |
O(n) |
O(1) |
|
| Leetcode 450 |
Delete Node in a BST |
O(logn) |
O(logn) |
|
| Leetcode 549 |
Binary Tree Longest Consecutive Sequence II |
__ |
__ |
|
| Leetcode 1339 |
Maximum Product of Splitted Binary Tree |
O(n) |
O(n) |
|
DFS & BFS
| # |
Title |
Time |
Space |
Remark |
| Leetcode 200 |
Number of Islands |
O(mn) |
O(min(m,n))~O(mn) |
BFS/DFS/Recursive |
| Leetcode 286 |
Walls and Gates |
O(mn) |
O(mn) |
BFS/DFS |
| Leetcode 130 |
Surrounded Regions |
O(mn) |
O(mn) |
DFS |
| Leetcode 339 |
Nested List Weight Sum |
O(n) |
O(n) |
BFS |
| Leetcode 364 |
Nested List Weight Sum II |
O(n) |
O(n) |
BFS |
| Leetcode 127 |
Word Ladder |
O(n*26^len) |
O(n) |
BFS |
| Leetcode 126 |
Word Ladder II |
O(n*26^len) |
O(n+p*l) |
BFS |
| Leetcode 695 |
Max Area of Island |
O(mn) |
O(mn) |
BFS |
| Leetcode 490 |
The Maze |
O(mn) |
O(mn) |
BFS |
| Leetcode 505 |
The Maze II |
O(mn*log(mn)) |
O(mn) |
Heap |
| Leetcode 675 |
Cut Off Trees for Golf Event |
O(mn*log(mn)) |
O(mn) |
|
| Leetcode 1436 |
Destination City |
__ |
__ |
|
| Leetcode 332 |
Reconstruct Itinerary |
__ |
__ |
|
| Leetcode 787 |
Cheapest Flights Within K Stops |
py |
O(n) |
Dijkstra |
| Leetcode 743 |
Network Delay Time |
__ |
__ |
Dijkstra |
| Leetcode 994 |
Rotting Oranges |
O(mn) |
O(mn) |
BFS |
| Leetcode 815 |
Bus Routes |
__ |
__ |
BFS |
| Leetcode 638 |
Shopping Offers |
__ |
__ |
|
| Leetcode 1269 |
Number of Ways to Stay in the Same Place After Some Steps |
__ |
__ |
|
| Leetcode 329 |
Longest Increasing Path in a Matrix |
__ |
__ |
|
| Leetcode 1197 |
Minimum Knight Moves |
__ |
__ |
BFS |
Backtracking
| # |
Title |
Time |
Space |
Remark |
| Leetcode 78 |
Subsets |
O(n*2^n) |
O(n) |
|
| Leetcode 90 |
Subsets II |
O(n*2^n) |
O(n) |
|
| Leetcode 77 |
Combinations |
O(k*Cnk) |
O(k)? |
|
| Leetcode 39 |
Combination Sum |
? |
O(n)? |
|
| Leetcode 40 |
Combination Sum II |
? |
O(n)? |
|
| Leetcode 216 |
Combination Sum III |
? |
O(n)? |
|
| Leetcode 254 |
Factor Combinations |
O(2^n)? |
O(n)? |
|
| Leetcode 46 |
Permutations |
O(n!) |
O(n) |
|
| Leetcode 47 |
Permutations II |
O(n!)? |
? |
|
| Leetcode 31 |
Next Permutation |
O(n) |
O(1) |
|
| Leetcode 60 |
Permutation Sequence |
O(n!) |
O(n) |
|
| Leetcode 291 |
Word Pattern II |
O(n*(Cnm) |
On) |
|
| Leetcode 17 |
Letter Combinations of a Phone Number |
O(3^n*4^m |
O(n) |
|
| Leetcode 282 |
Expression Add Operators |
O(n*4^n) |
O(n) |
|
| Leetcode 140 |
Word Break II |
O(n^2) |
O(n) |
|
| Leetcode 351 |
Android Unlock Patterns |
O(n!) |
O(n) |
|
| Leetcode 51 |
N-Queens |
O(n!) |
O(n) |
|
| Leetcode 52 |
N-Queens II |
O(n!) |
O(n) |
|
| Leetcode 491 |
Increasing Subsequences |
O(2^n) |
O(2^n) |
|
| Leetcode 1192 |
Critical Connections in a Network |
O(V+E) |
O(n) |
|
| Leetcode 93 |
Restore IP Addresses |
O(2^n) |
O(2^n) |
|
Backtracking 的时间复杂度
# 在backtracking函数中,for 循环里有几种选择就是几的n次方, 最少的2^n 例如 下面这种情况是O(3^n)
def bt(self,idx,n):
for i in range(idx, n):
self.bt()
self.bt()
self.bt()
# 在bt函数中,如果每次for循环都是T-1,那么时间复杂度 是 O(2^n)
def bt(self,idx,n):
for i in range(idx, n):
self.bt(i+1, n)
# 在bt函数中,如果每次for循环都是重新遍历(不重复上一步),那么时间复杂度 是 O(n!)
def bt(self,idx,n, visited):
for i in range(n):
if i not in visited:
visited.add(i)
self.bt(i+1, n, visited)
visited.remove(i)
Dynamic Programming
| # |
Title |
Time |
Space |
Remark |
| Leetcode 70 |
Climbing Stairs |
O(n) |
O(n) |
|
| Leetcode 62 |
Unique Paths |
O(n*m) |
O(n*m) |
Same as 64 |
| Leetcode 64 |
Minimum Path Sum |
O(m*n) |
O(m*n) |
|
| Leetcode 279 |
Perfect Squares |
O(n*n^0.5) |
O(n) |
Same as 322,377 |
| Leetcode 322 |
Coin Change |
O(s*n) |
O(s) |
|
| Leetcode 377 |
Combination Sum IV |
O(s*n) |
O(s) |
|
| Leetcode 139 |
Word Break |
O(n^2) |
O(n) |
|
| Leetcode 375 |
Guess Number Higher or Lower II |
O(n^3) |
O(n^2) |
|
| Leetcode 256 |
Paint House |
O(n) |
O(n) |
|
| Leetcode 265 |
Paint House II |
O(nk^2) |
O(nk) |
|
| Leetcode 72 |
Edit Distance |
O(mn) |
O(mn) |
|
| Leetcode 174 |
Dungeon Game |
O(mn) |
O(mn) |
|
| Leetcode 221 |
Maximal Square |
O(mn) |
O(mn) |
|
| Leetcode 85 |
Maximal Rectangle |
O(mn) |
O(mn) |
|
| Leetcode 312 |
Burst Balloons |
O(n^3) |
O(n^2) |
|
| Leetcode 198 |
House Robber |
O(n) |
O(n) |
|
| Leetcode 213 |
House Robber II |
O(n) |
O(n) |
|
| Leetcode 276 |
Paint Fence |
O(n) |
O(n) |
|
| Leetcode 91 |
Decode Ways |
O(n) |
O(n) |
|
| Leetcode 10 |
Regular Expression Matching |
O(mn) |
O(mn) |
|
| Leetcode 44 |
Wildcard Matching |
O(mn) |
O(mn) |
|
| Leetcode 1143 |
Longest Common Subsequence |
O(mn) |
O(mn) |
|
| Leetcode 472 |
Concatenated Words |
O(nl) |
O(l) |
|
| Leetcode 983 |
Minimum Cost For Tickets |
O(n) |
O(n) |
|
| Leetcode 368 |
Largest Divisible Subset |
O(n^2) |
O(n^2) |
|
Binary Search
| # |
Title |
Time |
Space |
Remark |
| Leetcode 278 |
First Bad Version |
__ |
__ |
|
| Leetcode 35 |
Search Insert Position |
__ |
__ |
|
| Leetcode 33 |
Search in Rotated Sorted Array |
__ |
__ |
|
| Leetcode 81 |
Search in Rotated Sorted Array II |
__ |
__ |
|
| Leetcode 153 |
Find Minimum in Rotated Sorted Array |
__ |
__ |
|
| Leetcode 154 |
Find Minimum in Rotated Sorted Array II |
__ |
__ |
|
| Leetcode 162 |
Find Peak Element |
__ |
__ |
|
| Leetcode 374 |
Guess Number Higher or Lower |
__ |
__ |
|
| Leetcode 34 |
Find First and Last Position of Element in Sorted Array |
__ |
__ |
|
| Leetcode 350 |
Intersection of Two Arrays II |
__ |
__ |
Two Pointer/HashMap/BS |
| Leetcode 300 |
Longest Increasing Subsequence |
O(nlogn)/O(n^2) |
O(n) |
BS/DP |
| Leetcode 354 |
Russian Doll Envelopes |
O(nlogn)/O(n^2) |
O(n) |
BS/DP |
| Leetcode 658 |
Find K Closest Elements |
__ |
__ |
|
Stack # Queue(or Heap)
| # |
Title |
Time |
Space |
Remark |
| Leetcode 155 |
Min Stack |
O(1) |
O(n) |
|
| Leetcode 232 |
Implement Queue using Stacks |
O(1) |
O(n) |
2 stacks |
| Leetcode 225 |
Implement Stack using Queues |
O(1)~O(n) |
O(n) |
2 queues |
| Leetcode 150 |
Evaluate Reverse Polish Notation |
O(n) |
O(n) |
|
| Leetcode 71 |
Simplify Path |
O(n) |
O(n) |
|
| Leetcode 394 |
Decode String |
O(n) |
O(n) |
2 stacks |
| Leetcode 224 |
Basic Calculator |
O(n) |
O(n) |
2 stacks |
| Leetcode 227 |
Basic Calculator II |
O(n) |
O(n) |
|
| Leetcode 385 |
Mini Parser |
O(n) |
_O(n)klkj _ |
|
| Leetcode 84 |
Largest Rectangle in Histogram |
O(n) |
O(n) |
|
| Leetcode 215 |
Kth Largest Element in an Array |
O(nlogn) |
O(n) |
|
| Leetcode 347 |
Top K Frequent Elements |
O(n) |
O(n) |
bucket sort |
| Leetcode 692 |
Top K Frequent Words |
O(nlogn) |
O(n) |
bucket sort |
| Leetcode 218 |
The Skyline Problem |
O(nlogn) |
O(n) |
|
| Leetcode 341 |
Flatten Nested List Iterator |
O(n) |
O(N) |
|
| Leetcode 373 |
Find K Pairs with Smallest Sums |
O(klogk) |
O(k) |
|
| Leetcode 378 |
Kth Smallest Element in a Sorted Matrix |
O(klogk) |
O(k) |
|
| Leetcode 1439 |
Find K Pairs with Smallest Sums of Matrix |
__ |
__ |
|
| Leetcode 739 |
Daily Temperatures |
O(n) |
O(n) |
|
| Leetcode 621 |
Task Scheduler |
__ |
__ |
|
Matrix
| # |
Title |
Time |
Space |
Remark |
| Leetcode 48 |
Rotate Image |
__ |
__ |
|
| Leetcode 54 |
Spiral Matrix |
__ |
__ |
|
| Leetcode 59 |
Spiral Matrix II |
__ |
__ |
|
| Leetcode 1439 |
Find the Kth Smallest Sum of a Matrix With Sorted Rows |
__ |
__ |
Divide&Conquer |
| Leetcode 1311 |
Sparse Matrix Multiplication |
__ |
__ |
|
| Leetcode 1378 |
Kth Smallest Element in a Sorted Matrix |
__ |
__ |
|
| Leetcode 174 |
Search a 2D Matrix |
__ |
__ |
|
| Leetcode 1240 |
Search a 2D Matrix II |
O(m+n) |
O(1) |
|
| Leetcode 179 |
Word Search |
__ |
__ |
|
| Leetcode 1219 |
Path with Maximum Gold |
__ |
__ |
Same as word search |
| Leetcode 1361 |
Bomb Enemy |
__ |
__ |
|
| Leetcode 136 |
Valid Sudoku |
__ |
__ |
|
| Leetcode 137 |
Sudoku Solver |
__ |
__ |
BackTracking |
| Leetcode 909 |
Snakes and Ladders |
__ |
__ |
BFS |
| Leetcode 1102 |
Path With Maximum Minimum Value |
__ |
__ |
Greedy |
| Leetcode 296 |
Best Meeting Point |
__ |
__ |
BFS |
| Leetcode 317 |
Shortest Distance from All Buildings |
__ |
__ |
BFS |
LinkedList
| # |
Title |
Time |
Space |
Remark |
| Leetcode 206 |
Reverse Linked List |
__ |
__ |
|
| Leetcode 141 |
Linked List Cycle |
__ |
__ |
|
| Leetcode 24 |
Swap Nodes in Pairs |
__ |
__ |
|
| Leetcode 328 |
Odd Even Linked List |
__ |
__ |
|
| Leetcode 92 |
Reverse Linked List II |
__ |
__ |
|
| Leetcode 237 |
Delete Node in a Linked List |
__ |
__ |
|
| Leetcode 19 |
Remove Nth Node From End of List |
__ |
__ |
|
| Leetcode 83 |
Remove Duplicates from Sorted List |
__ |
__ |
|
| Leetcode 203 |
Remove Linked List Elements |
__ |
__ |
|
| Leetcode 82 |
Remove Duplicates from Sorted List II |
__ |
__ |
|
| Leetcode 369 |
Plus One Linked List |
__ |
__ |
|
| Leetcode 2 |
Add Two Numbers |
__ |
__ |
|
| Leetcode 160 |
Intersection of Two Linked Lists |
__ |
__ |
|
| Leetcode 21 |
Merge Two Sorted Lists |
__ |
__ |
|
| Leetcode 234 |
Palindrome Linked List |
__ |
__ |
|
| Leetcode 143 |
Reorder List |
__ |
__ |
|
| Leetcode 142 |
Linked List Cycle II |
__ |
__ |
|
| Leetcode 148 |
Sort List |
__ |
__ |
Merge sort(Divide&Conquer) |
| Leetcode 25 |
Reverse Nodes in k-Group |
__ |
__ |
Recursive |
| Leetcode 61 |
Rotate List |
__ |
__ |
|
| Leetcode 86 |
Partition List |
__ |
__ |
Two Pointer |
| Leetcode 23 |
Merge k Sorted Lists |
__ |
__ |
Merge sort |
| Leetcode 147 |
Insertion Sort List |
__ |
__ |
Insertion sort |
Toplogical Sort
| # |
Title |
Time |
Space |
Remark |
| Leetcode 207 |
Course Schedule |
__ |
__ |
|
| Leetcode 210 |
Course Schedule II |
__ |
__ |
|
| Leetcode 269 |
Alien Dictionary |
__ |
__ |
|
Bit Manipulation
| # |
Title |
Time |
Space |
Remark |
| Leetcode 136 |
Single Number |
__ |
__ |
|
| Leetcode 318 |
Maximum Product of Word Lengths |
__ |
__ |
|
Random
| # |
Title |
Time |
Space |
Remark |
| Leetcode 384 |
Shuffle an Array |
__ |
__ |
|
| Leetcode 398 |
Random Pick Index |
__ |
__ |
|
| Leetcode 382 |
Linked List Random Node |
__ |
__ |
|
| Leetcode 380 |
Insert Delete GetRandom O(1) |
__ |
__ |
|
| Leetcode 381 |
Insert Delete GetRandom O(1) - Duplicates allowed |
__ |
__ |
|
Graph
| # |
Title |
Time |
Space |
Remark |
| Leetcode 133 |
Clone Graph |
__ |
__ |
|
| Leetcode 138 |
Copy List with Random Pointer |
O(n) |
O(n) |
|
| Leetcode 399 |
Evaluate Division |
__ |
__ |
DFS |
| Leetcode 310 |
Minimum Height Trees |
__ |
__ |
Topological Sort |
| Leetcode 1152. Analyze User Website Visit Pattern |
__ |
__ |
Topological Sort |
|
Union Find
| # |
Title |
Time |
Space |
Remark |
| Leetcode 261 |
Graph Valid Tree |
__ |
__ |
UF/DFS |
| Leetcode 323 |
Number of Connected Components in an Undirected Graph |
__ |
__ |
UF/DFS |
| Leetcode 305 |
Number of Islands II |
__ |
__ |
|
Trie
| # |
Title |
Time |
Space |
Remark |
| Leetcode 208 |
Implement Trie (Prefix Tree) |
__ |
__ |
|
| Leetcode 211 |
Add and Search Word - Data structure design |
__ |
__ |
DFS with Trie |
| Leetcode 212 |
Word Search II |
__ |
__ |
BackTrakcing with Trie |
| Leetcode 642 |
Design Search Autocomplete System |
__ |
__ |
|
| Leetcode 588 |
Design In-Memory File System |
__ |
__ |
|
| Leetcode 635 |
Design Log Storage System |
__ |
__ |
|
Design
| # |
Title |
Time |
Space |
Remark |
| Leetcode 359 |
Logger Rate Limiter |
__ |
__ |
Buffer |
| Leetcode 362 |
Design Hit Counter |
__ |
__ |
Buffer |
| Leetcode 346 |
Moving Average from Data Stream |
__ |
__ |
|
| Leetcode 281 |
Zigzag Iterator |
__ |
__ |
|
| Leetcode 284 |
Peeking Iterator |
__ |
__ |
|
| Leetcode 251 |
Flatten 2D Vector |
__ |
__ |
|
| Leetcode 146 |
LRU Cache |
__ |
__ |
Doubly liked list |
| Leetcode 460 |
LFU Cache |
O(1) |
O(n) |
Doubly liked list |
| Leetcode 303 |
Range Sum Query - Immutable |
__ |
__ |
PreSum |
| Leetcode 170 |
Two Sum III - Data structure design |
__ |
__ |
|
| Leetcode 348 |
Design Tic-Tac-Toe |
__ |
__ |
|
| Leetcode 353 |
Design Snake Game |
__ |
__ |
|
| Leetcode 355 |
Design Twitter |
__ |
__ |
OOD |
| Leetcode 706 |
Design HashMap |
__ |
__ |
|
| Leetcode 622 |
Design Circular Queue |
__ |
__ |
|
| Leetcode 895 |
Maximum Frequency Stack |
__ |
__ |
|
| Leetcode 307 |
Range Sum Query - Mutable |
O(logn)~O(n) |
O(n) |
Segment Trees |
Non-Leetcode
| # |
Title |
Time |
Space |
Remark |
|
First Unique Number |
__ |
__ |
Doubly liked list |
|
Integer to Chinese |
__ |
__ |
|
|
Print Nodes in Top View of Binary Tree |
__ |
__ |
|
|
Bottom View of Binary Tree |
__ |
__ |
|
|
K Decimal Addition |
__ |
__ |
|