- Array
- Greedy
- Tree
- Tree Relevant
- Math
- String
- Hash Table
- Bit Manipulation
- Stack
- Queue
- Heap
- Linked List
- Two Pointer
- Sort
- Recursion
- Binary Search
- Binary Search Tree
- Depth First Search
- Backtracking
- Dynamic Programming
- Regular Expression Summary
- Sliding Window Summary
- Graph
- Design
- Bash
๐ good algorithm
โ๏ธ smart code design
๐
: good question
โ: not good designed question
ๅ ไธชๅ็ฌ็ฎๆณ:
- Trie
- Union Find
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 102. Binary Tree Level Order Traversal | O(n) | O(n) | Medium | |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 015. 3 Sum | O(n^2) | O(1) | Medium | ๐้ฎ้ขๅ ณ้ฎๆฏsort + skip duplicate |
| 016. 3 Sum Closest | O(n^2) | O(1) | Medium | ๐sort + two pointer๏ผๆ นๆฎthree sum ๅsorted list็งปๅจไธคไธชpointers |
| 018. 4 Sum | O(n^3) | O(1) | Medium | ๐sort + two pointer๏ผๆ่ทฏๅ015. 3 Sum ไธๆ ท |
| 026. Remove Duplicates from Sorted Array | O(n) | O(1) | Easy | Two pointer |
| 027. Remove Element | O(n) | O(1) | Easy | Two pointer |
| 031. Next Permutation | O(n) | O(1) | Medium | ่ท556. Next Greater Element III ๆ่ทฏ็ฑปไผผ, C++ๅฏไปฅ็จis_sorted_until + upper_bound() |
| 041. First Missing Positive | O(n) | O(1) | Hard | ๐ๅ ็ฝฎๆข, ๆๆฏไธชๅ ็ด ๆพๅจๅ้ไฝ็ฝฎ๏ผๅ็A[i] == i+1 ? ไธ็ญไบ return i+1, ๆๅๅฆๆ่ฟๆฒกreturn, return size +1 |
| 048. Rotate Image | O(n^2) | O(1) | Medium | ๐
|
| 054. Spiral Matrix | O(m*n) | O(1) | Medium | ๐ๅฎไน up, down, left, right ๅไธช่พน็๏ผๆฏๆฌกloop ๅจๆๅคๅด็ไธๅ |
| 059. Spiral Matrix II | O(n^2) | O(1) | Medium | ๐ๆ่ทฏ่ท048. Rotate Image ๅ 054. Spiral Matrix ็ฑปไผผ |
| 066. Plus One | O(n) | O(1) | Easy | |
| 073. Set Matrix Zeroes | O(m*n) | O(1) | Medium | ๐two pass:1. ๆๅฆๆmatrix[i][j] == 0, ๆmatrix[i][0] ๅmatrix[0][j] ่ฎพไธบ0, ๅฆๆ็ฌฌไธๅ่ฎพ0ไนๅ๏ผๆๆฐไธบ0๏ผ่ฎพcol0 = 0ใ 2.ไปไธๅพไธloop, ็ขฐๅฐmatrix[i][0]] or matrix[0][j] ไธบ0, matrix[i][j] = 0, if col0 == 0, matrix[i][0] = 0 |
| 080. Remove Duplicates from Sorted Array II | O(n) | O(1) | Medium | |
| 118. Pascal's Triangle | O(n^2) | O(1) | Easy | |
| 119. Pascal's Triangle II | O(n^2) | O(1) | Easy | Easy DP |
| 121. Best Time to Buy and Sell Stock | O(n) | O(1) | Easy | |
| 128. Longest Consecutive Sequence | O(n) | O(n) | Hard | ๐
|
| 169. Majority Element | O(n) | O(1) | Easy | |
| 189. Rotate Array | O(n) | O(1) | Easy | |
| 209. Minimum Size Subarray Sum | O(n) | O(1) | Medium | ๐
|
| 215. Kth Largest Element in an Array | O(n) ~ O(n^2) | O(1) | Medium | ๐
|
| 228. Summary Ranges | O(n) | O(1) | Medium | |
| 229. Majority Element II | O(n) | O(1) | Medium | ๐Boyer-Moore Majority Vote algorithm |
| 238. Product of Array Except Self | O(n) | O(1) | Medium | ๐res[i]่กจ็คบ nums[0: i-1]็ไน็งฏ๏ผright ่ฎฐๅฝไป็ปๅฐพๅฐnums[i+1: end]็ไน็งฏ. ๆๅres[i] = res[i] * right; ไนๅฏไปฅ็จleft, right One Pass |
| 240. Search a 2D Matrix II | O(n+m) | O(1) | Medium | ๐sorted matrix้ข็ฎ็ๅ ณ้ฎๆฏไป็ฌฌไธ่กๆๅไธไธชๅผๅง๏ผๅฆๆๅฝๅๆฐๆฏๆณ่ฆ็ๅคง, --col, ๅฆๆๅฝๅๆฐๆฏๆณ่ฆ็ๅฐ๏ผ++row |
| 289. Game of Life | O(m * n) | O(1) | Medium | ๐่ท238. Product of Array Except Selfๆไธ็น็น็ฑปไผผ๏ผๅ ๅๅmatrixๅฐๆณ่ฆ็ๆ ผๅผ, ็ถๅๅๅtransformๅฐ็ปๆ: ๆไธไธไปฃๆดป็ |
| 334. Increasing Triplet Subsequence | O(n) | O(1) | Medium | ๐็จไธคไธชๆฐ่กจ็คบb, c, c่กจ็คบๅฝๅๆๅฐ, b่กจ็คบๅฝๅ็ฌฌไบๅฐ, ๅฝi้ฝๅคงไบ่ฟไธคไธชๆฐ๏ผreturn true, ไธ็จๆ ๅฟiๅชๆดๆฐๆดๆฐc, ๅ ไธบ็ญๆกๅฟ ้กป่ฆ่ฟ่ฟb |
| 384. Shuffle an Array | O(n) | O(n) | Medium | C++ srand(time(NULL)); rand(); uniform_int_distribution |
| 396. Rotate Function | O(n) | O(1) | Medium | ๐mathematical induction F(k) = F(k-1) + sum - nBk[-k] |
| 412. Fizz Buzz | O(n) | O(1) | Easy | |
| 414. Third Maximum Number | O(n) | O(1) | Easy | |
| 419. Battleships in a Board | O(n*m) | O(1) | Medium | ๐็ๆบๅคด๏ผif [i][j] = 'X' ไธ [i-1][j] ๅ [i][j-1] ๅฆๆ้ฝไธๆฏX๏ผcount += 1 |
| 442. Find All Duplicates in an Array | O(n) | O(1) | Medium |
|
| 448. Find All Numbers Disappeared in an Array | O(n) | O(1) | Medium | ๆ่ทฏไธ442. Find All Duplicates in an Arrayไธๆจกไธๆ ท๏ผไธค็งๆนๆณไนไธๆ ท |
| 565. Array Nesting | O(n) | O(1) | Medium | DFS, ๆvisit็็นๅไธบ-1, nest arrayๆฏๅพช็ฏ๏ผๆไปฅ่ตท็นๆ ่ฎบๆฏๅชไธช็น่ฟๅ ฅ้ฝๅฏไปฅๅพๅฐๅฎๆด็ๅพช็ฏ, ๆฏๅฆ a->b->c->d->a ไธไผๆ a->b->c->d->b |
| 566. Reshape the Matrix | O(m*n) | O(1) | Easy | |
| 581. Shortest Unsorted Continuous Subarray | O(n) | O(1) | Easy | ๐
|
| 605. Can Place Flowers | O(n) | O(1) | Easy | |
| 643. Maximum Average Subarray I | O(n) | O(1) | Easy | ๆ็ฎๅ็sliding window |
| 661. Image Smoother | O(n) | O(1) | Easy | ่ท289. Game of Lifeๆ่ทฏไธๆ ท๏ผ ไธ็นไธไธๆ ท็ๆฏๆไธไธไปฃ็ๆฐๅณ็งป8ไธชbit, ไนๅๅ็ฌฌไบๆฌกpass matrix, ๆฏไธช็น>>8 ๅทฆ็งป8ไธชbits |
| 665. Non-decreasing Array | O(n) | O(1) | Easy | ๐ไธค็งoperation: 1.nums[i-1] = nums[i] (้), nums[i] = nums[i-1] (ๅ), ้ไผไบๅ |
| 667. Beautiful Arrangement II | O(n) | O(1) | Meidum | ๐brainstorm |
| 670. Maximum Swap | O(n) | O(1) | Medium | ๐
|
| 674. Longest Continuous Increasing Subsequence | O(n) | O(1) | Easy | |
| 697. Degree of an Array | O(n) | O(n) | Easy | |
| 713. Subarray Product Less Than K | O(n) | O(1) | Medium | ๐๐ Sliding Window |
| 845. Longest Mountain in Array | O(n) | O(1) | Medium | ๐ธ |
| 918. Maximum Sum Circular Subarray | O(n) | O(1) | Medium | ๐ ๐ Kadane's algorithm |
| 997. Find the Town Judge | O(n+t) | O(n) | Easy | ๐ In-degree, out-degree |
| 1375. Bulb Switcher III | O(n) | O(1) | Medium | |
| 1380. Lucky Numbers in a Matrix | O(m*n) | O(m+n) | Easy | zip(*m)่ทๅพcolumn in list, set intersection |
| 1389. Create Target Array in the Given Order | O(n^2) | O(1) | Easy | ย โ |
| 1394. Find Lucky Integer in an Array | O(n) | O(n) | Easy | ย :pencil2: Loop C++ Map Key Value |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 011. Container With Most Water | O(n) | O(1) | Medium | |
| 042. Trapping Rain Water | O(n) | O(1) | Hard | Greedy/Descending Stack |
| 045. Jump Game II | O(n) | O(1) | Hard | ๐ |
| 055. Jump Game | O(n) | O(1) | Medium | |
| 122. Best Time to Buy and Sell Stock II | O(n) | O(1) | Medium | |
| 134. Gas Station | O(n) | O(1) | Medium | ๐ |
| 135. Candy | O(n) | O(n) O(1) | Hard | ๐ |
| 316. Remove Duplicate Letters | O(n) | O(k) | Hard | ๐ ๐ ๐ Tricky |
| 321. Create Maximum Number | O((m+n)^3) | O(k) | Hard | ๐ ๐ Try all and compare(Not a good question) |
| 330. Patching Array | O(s + logn) | O(1) | Hard | ๐ ๐ ๐ Hint |
| 376.Wiggle Subsequence | O(n) | O(1) | Medium | ๐ |
| 392. Is Subsequence | O(n) | O(1) | Easy | โ:pencil2: two pointer or C++ iterator; follow-upๅฏไปฅ็จbinary search; iter |
| 397. Integer Replacement | O(log(n)) | O(1) | Medium | Math |
| 402. Remove K Digits | O(n) | O(n) | Medium | ๐ ascending stack(string ๅฏไปฅๅstack) |
| 435. Non-overlapping Intervals | O(nlogn) | O(1) | Medium | Sort ็ฑปไผผ็้ข |
| 452. Minimum Number of Arrows to Burst Balloons | O(nlogn) | O(1) | Medium | Sort ็ฑปไผผ็้ข
|
| 455. Assign Cookies | O(nlogn) | O(1) | Easy | โ |
| 621. Task Scheduler | O(n) | O(1) | Medium | ๐ |
| 630. Course Schedule III | O(nlogn) | O(k) | Hard | ๐ ็ฑปไผผ็้ข |
| 646. Maximum Length of Pair Chain | O(nlogn) | O(1) | Medium | ็ฑปไผผ็้ข |
| 649. Dota2 Senate | O(n) | O(n) | Medium | Queue |
| 659. Split Array into Consecutive Subsequences | O(n) | O(n) | Medium | ๐ |
| 738. Monotone Increasing Digits | O(1) | O(1) | Medium | |
| 757. Set Intersection Size At Least Two | O(nlogn) | O(1) | Hard | ๐ ๐ ่พน็้ๆๅคง็ไธคไธช๏ผ่ไธๆฏไธๅคงไธๅฐ |
| 763. Partition Labels | O(n) | O(n) | Medium | hashmap/sliding windows |
| 767. Reorganize String | O(n) | O(1) | Medium | priority_queue |
| 798. Smallest Rotation with Highest Score | O(n) | O(1) | Hard | ๐ ๐ ๐ |
| 843. Guess the Word | O(n^2) | O(n) | Hard | |
| 861. Score After Flipping Matrix | O(m * n) | O(1) | Medium | |
| 870. Advantage Shuffle | O(nlogn) | O(n) | Medium | ๐๐ sort \ maxheap \ minheap |
| 881. Boats to Save People | O(nlogn) | O(n) | Medium | two pointer |
| 936. Stamping The Sequence | O((n - m) * m)) | O((n - m) * m)) | Hard | ๐ ๐ ๐ , ่ฟๅฏไปฅ็จDFS |
| 948. Bag of Tokens | O(nlogn) | O(1) | Medium | Bad Problem Description. Rewrite Version |
| 962. Maximum Width Ramp | O(n) | O(n) | Medium | ๐๐ ๐ |
| 968. Binary Tree Cameras | O(n) | O(h) | Hard | ๐ |
| 984. String Without AAA or BBB | O(a+b) | O(1) | Medium | |
| 995. Minimum Number of K Consecutive Bit Flips | O(n) | O(1) | Hard | ๐๐ |
| 1249. Minimum Remove to Make Valid Parentheses | O(n) | O(1) | Medium | Stack |
| 1386. Cinema Seat Allocation | O(n) | O(n) | Medium | โ |
| 1419 Minimum Number of Frogs Croaking | O(n) | O(1) | Medium | ้ไฟ่ฏ counter ้ๅข c>r>o>a>k |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
//Inorder Traversal
//stack,
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>res;
stack<TreeNode*>stk;
while(root || !stk.empty()){
if(root){
// res.push_back(cur->val); //Preorder
stk.push(root);
root = root->left;
}else{
root = stk.top(); stk.pop();
// res.push_back(root->val); //Inorder
root = root->right;
}
}
return res;
}
};
//Postorder
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int>res;
TreeNode* cur = root;
while(cur ||!stk.empty()){
if(cur){
res.push_back(cur->val);
stk.push(cur);
cur = cur->right;
}else{
cur = stk.top(); stk.pop();
cur = cur->left;
}
}
reverse(res.begin(), res.end());
return res;
}
};
//Morris: ๆต็จๅพ่ง, 094. Binary Tree Inorder Traversal.cpp
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>res;
TreeNode* cur = root;
while(cur){
if(!cur->left)
{
//res.push_back(cur->val); //Inorder, preorder
cur = cur->right;
}else{
TreeNode* pre = cur->left;
while(pre->right && pre->right!=cur)
pre = pre->right;
if(pre->right){
//res.push_back(cur->val); //Inorder
pre->right = NULL;
cur = cur->right;
}
else{
//res.push_back(cur->val); //Pre-order
pre->right = cur;
cur = cur->left;
}
}
}
return res;
}
};
//PostOrder
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int>res;
TreeNode* cur = root;
while(cur){
if(!cur->right){
res.push_back(cur->val);
cur = cur->left;
}else{
TreeNode* pre = cur->right;
while(pre->left && pre->left != cur)
pre = pre->left;
if(pre->left){
pre->left = NULL;
cur = cur->left;
}else{
res.push_back(cur->val);
pre->left = cur;
cur = cur->right;
}
}
}
reverse(res.begin(), res.end());
return res;
}
};
//ๅฆๆๆright child, ็ป่ฟroot ไธคๆฌก
//112. Path Sum https://leetcode.com/problems/path-sum/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
stack<TreeNode*>stk;
TreeNode* cur = root, *pre = nullptr;
while(cur || !stk.empty()){
if(cur){
stk.push(cur);
sum -= cur->val;
cur = cur->left;
}else{
cur = stk.top();
if(!cur->right && !cur->left && sum == 0)
return true;
if(cur->right && cur->right != pre){
cur = cur->right;
}
else{
pre = cur;
sum += cur->val;
cur = nullptr;
stk.pop();
}
}
}
return false;
}
};
//In order traversal, ไธๅไบไนๅ็iterative ่งฃ, ่ฟๆฏๆฏไธชnode ้ฝๅ
่ขซpush ่ฟstack, ๅชๆreturn backๆถๅๆpop
/*
่ฏฆ่ง 236. Lowest Common Ancestor of a Binary Tree
https://github.com/beckswu/Leetcode/blob/master/DFS/236.%20Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree.cpp#L32๏ผ
1
/
2
\
3
ๆไธ้ข็inorder ็ stack ๅฐ3ๆถๅๆฏ [1๏ผ3
ไธ้ข่งฃ็stack ๆฏ ๅฐ3ๆฏ [1,2,3]
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//iterative, path comparing
if(!root ) return root;
vector<TreeNode*> path;
if(root)
path.push_back(root); //tempๆฏstack๏ผๅ
็ด ๆฏไปrootๅฐ็ฐๅจnodeไธ็่ทฏๅพ
TreeNode *prev = nullptr;
while(!path.empty()){
root=temp.back();
if(!root->left && !root->right || !root->right && prev==root->left || root->right && prev==root->right){
path.pop_back();
prev=root;
}
else{
if(!root->left || prev==root->left) path.push_back(root->right);
else path.push_back(root->left);
}
}
}
};
TreeNode* helper(TreeNode** head ){
int val = *head; //่ทๅๅผ, ๆฏๅฆๅผๆฏ5,
TreeNode** cur = head; //
head = &((*head)->left); //ไธไผๅฝฑๅไนๅcur็ๅผ๏ผ ๆhead assign ไธไธชๆฐobject, ไนๅ็ปๅฎhead็ๅฐๅ(cur)็object ๅนถๆฒกๆๅ ้ค
*head = (*head)->left; //ไผๅฝฑๅcur็ๅผ๏ผ *head ๅๅฐๅ, ๆนๅhead่ฟไธชๅฐๅ็ปๅฎ็ๅผ, ๅ ไธบcur ๅheadๅฐๅไธๆ ท , ๆไปฅcur็ๅผไนๆนๅ
return cur;
}
//ๆฏๅฆ:
void helper(int *p){
int *newp = p;
*p = 5; //ไผๅฝฑๅnewp็ๅผ, ๅ ไธบnewp ๅ pๅฐๅไธๆ ท๏ผๆดๆน็p็ๅผ๏ผ newp่ชๅจไผๆดๆน
p = new int(10); // ไธไผๆดๆนnewp ็ๅผ, ๅ ไธบp็ๅฐๅ่ขซๆขๆไบ, ไนๅ็ปๅฎp็ๅฐๅๅนถๆฒกๆๅ ้ค
}
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 094. Binary Tree Inorder Traversal | O(n) | O(1) | Medium | ๐๐Morris Traversal, ็ฐๅจ็น่ฟๅจ left-child ๆๅณไพง็node ๅณไพง, ๅ ไธบๆๅณไพง็node ๆๅvisit |
| 099 Recover Binary Search Tree | O(n) | O(1) | Hard | ๐๐ ่ฐๆขnode ไน้ด็ฌฌไธไธชๆ้่ฏฏ็๏ผไนๆฏๆๅคง็prev๏ผ๏ผๅๆๅไธไธช้่ฏฏ๏ผไนๆฏๆๅฐ็cur๏ผ๏ผ๐ก้กบๅบไธๅฎๆฏinorder๏ผ็ฑๅฐๅฐๅคง |
| 144. Binary Tree Preorder Traversal | O(n) | O(1) | Medium | Morris Traversal,ๆณจๆpreorder ไธinorder push ่ฟvector็้กบๅบ็ๅบๅซ |
| 145. Binary Tree Postorder Traversal | O(n) | O(1) | Hard | = ๅ right ๅleft ็ inorder traversal ๐Morris Traversal |
| 208. Implement Trie (Prefix Tree) | O(n) | O(1) | Medium | Trie |
| 211. Add and Search Word - Data structure design | O(min(n, h)) | O(min(n, h)) | Medium | Trie + DFS |
| 226. Invert Binary Tree | O(n) | O(h), O(w)) | Easy | ๐ฝ ไธๅฏไปฅ left = invert(right); right = invert(left);, ๅ ไธบleft ๅจinvert rightๆถๅๆนๅ |
| 297. Serialize and Deserialize Binary Tree | O(n) | O(h) | Hard | โ๏ธostringstream & istringstream ็จๆณ, BFS๏ผ> pointer of pointer ๅญpointer ๅฐๅ |
| 307. Range Sum Query - Mutable | O(n), O(logn) | O(n) | Medium | โ๏ธ BIT & Segment Tree; BIT tree ้่ฆarrไฝไธบๅ็ ง็ฉ,ๆฏๆฌกๆ นๆฎval-arr[i]็update, update่ฟๅarr[i] = val |
| 525. Contiguous Array | O(n) | O(n) | Medium | ๐ๆๆๆ็0ๅๆ-1๏ผ ๆไปฅๅฝๆsum[i,j] = 0ๆถ => [i,j]ไธญๆๅ็ญ็1 ๅ 0๏ผ same as 325. Maximum Size Subarray Sum Equals k |
| 529. Minesweeper | O(m * n) | O(m + n) | Medium | โ ็ฎๅDFS |
| 538. Convert BST to Greater Tree | O(n) | O(h) | Easy | ๐ๆณจๆPython BFS |
| 543. Diameter of Binary Tree | O(n) | O(h) | Easy | ๐ๅ ๅฐฝๅฏ่ฝdfs๏ผๅๆฏ่พheight ไผๆดๅฟซ |
| 563. Binary Tree Tilt | O(n) | O(n) | Easy | โๆ่ทฏ่ท543. Diameter of Binary Tree ไธๆ ท |
| 572. Subtree of Another Tree | O(m * n) | O(h) | Easy | ๐ seralization |
| 606. Construct String from Binary Tree | O(n) | O(h) | Easy | โ Easy Recursion |
| 617. Merge Two Binary Trees | O(n) | O(h) | Easy | ๐ |
| 623. Add One Row to Tree | O(n) | O(h) | Medium | ๐ |
| 637. Average of Levels in Binary Tree | O(n) | O(h) | Easy | โ |
| 652. Find Duplicate Subtrees | O(n) | O(n) | Medium | ๐๐ Seralization(String็memory ๆฏ O(n^2)) / Hash, C++ ๆๅฎไนhash. ๆณจ: ๆ ้กปseralize ๅฎๆดๅๅๅฏปๆพ, analysis |
| 653. Two Sum IV - Input is a BST | O(n) | O(h) | Easy | ๐๐ๅฏไปฅ่ๆไนๅ BST Iterator |
| 654. Maximum Binary Tree | O(n) | O(h) | Medium | ๐๐๐ก descending stack:
|
| 655. Print Binary Tree | O(n) | O(h) | Medium | Mathๆพ่งๅพ |
| 662. Maximum Width of Binary Tree | O(n) | O(h) | Medium | โ Math ๆพ่งๅพ, ้ป่พ่ท655. Print Binary Tree็ฑปไผผ |
| 677. Map Sum Pairs | O(n) | O(t) | Medium | โSimple Trie |
| 684. Redundant Connection | O(n) | O(n) | Medium | ๐Union Find ๅฆๆไธคไธชnode ่ฟๆฅไนๅๅ็ฐparent ๅทฒ็ปไธๆ ท๏ผ่กจ็คบไนๅไธคไธชnodesๅทฒ็ป่ฟๆฅ๏ผๅฆๆๅ่ฟๆฅedge๏ผไผๆๆcycle |
| 685. Redundant Connection II | O(n) | O(n) | Hard | Union Find ๆณจๆๆๆtree ็ๆกไปถ, ไธ่ฝๆไธไธชchild ่ฟไธไธคไธชparent, ็ถๅๅปๆ่ฟไธชchildไธไธช้พ๏ผไฟ่ฏ้ฝๆฏไธไธชchildๅฏนๅบไธไธชparent, ๅ็ๆๆฒกๆcycle, ๆฒกๆcycle่กจ็คบๅป้พๅปๆๅไบ, ๆcycle ่กจ็คบๅป้พๅป้ไบ |
| 687. Longest Univalue Path | O(n) | O(h) | Easy | ๐ Really good Recussive Question! |
| 699. Falling Squares | O(nlogn) | O(n) | Hard | ๐Good Question! ่ฅๆณๆพ็นๅฑไบ ๅชไธช่ๅดไนไธญ ๆฏๅฆ 3โ (1,5) or (7,9) , ็จmap + binary search
|
| 814. Binary Tree Pruning | O(n) | O(h) | Medium | ๐Really good question! |
| 850. Rectangle Area II | O(nlogn) | O(h) | Hard | ๐๐ก่ท699. Falling Squaresๆ่ทฏๆ็นๅ, ๆ นๆฎheightไธๅฑไธๅฑ็็ฎๅฝๅฑ้ฟๆนไฝ้ข็งฏ,็ฎๅฎ้ข็งฏๅๆดๆฐไธไธๅฑ็ๅบcurx |
| 863. All Nodes Distance K in Binary Tree | O(n) | O(h) | Medium | ๐๐Really good question! ไธๅฟ ็บ ็ปไบone pass, ้่ฆchild -> parent map |
| 865. Smallest Subtree with all the Deepest Nodes | O(n) | O(h) | Medium | ๐ ่ฅleft, right child ้ฝๆฏๆๆทฑ็, ๅrootไธบ ๆๆทฑ็node |
| 889. Construct Binary Tree from Preorder and Postorder Traversal | O(n) | O(h) | Medium | ๐๐
|
| 1008. Construct Binary Search Tree from Preorder Traversal | O(n) | O(h) | Medium | ๐ Stack, Recursion, Morris Traversal |
| 1028. Recover a Tree From Preorder Traversal | O(n) | O(h) | Hard | ๐ stack / DFS, stack้ป่พ็ฑปไผผ889. Construct Binary Tree from Preorder and Postorder Traversal |
| 1409. Queries on a Permutation With Key | O(nlogn) | O(n) | Medium | BIT, Fenwick Tree, ๐ How to Build FenwickTree |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 007. Reverse Integer | O(1) | O(1) | Easy | |
| 009. Palindrome Number | O(1) | O(1) | Easy | |
| 012. Integer to Roman | O(n) | O(1) | Medium | |
| 013. Roman to Integer | O(n) | O(1) | Easy | |
| 964. Least Operators to Express Number | O(logn) | O(logn) | Hard | ๐ ๐ ๐ |
| 1360. Number of Days Between Two Dates | O(1) | O(1) | Easy | |
| 1362. Closest Divisors | O(sqrt(n)) | O(1) | Medium | |
| 1363. Largest Multiple of Three | O(n) | O(1) | Hard | |
| 1390. Four Divisors | _O(n * sqrt(n)) _ | O(1) | Medium | โ |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 005.Longest Palindromic Substring | O(n) | O(n) | Medium | ๐ manacher(้ฉฌๆ่ฝฆ็ฎๆณ), mx่กจ็คบๅฝๅๆ้ฟๅๆๅคๅณไพง็ฌฌไธ็น, idๆฏๅฝๅๅๆไธญๅฟ, p[i]่กจ็คบๅฝๅๆ้ฟๅๆ, if i<mx, p[i] = min(p[2id-i], p[i]) |
| 006. ZigZag Conversion | O(n) | O(n) | Medium |
|
| 008. String to Integer (atoi) | O(n) | O(1) | Easy | C++ๅฏไปฅ็จfind_first_not_of |
| 014. Longest Common Prefix | O(n) | O(1) | Easy | loopๆๆๆฐ็ฌฌ0ไฝๅฐ็ฌฌiไฝ๏ผ็ดๅฐไธ็ธๅ,่ฟๅstr[0].substr(0,i) |
| 028. Implement strStr() | O(n+k) | O(k) | Easy | kmp algorithm: prefix array[i]่กจ็คบi็น็ๆ้ฟ็prefix ไนๆฏsuffix้ฟๅบฆ ๆฏๅฆ"ABA", ็ฌฌไธไธชa็ๆ้ฟ็prefix ไนๆฏsuffix ็้ฟๅบฆๆฏ1 A ่prefix array[i], ไฝไธบindex, ๆฏๅฝๅๆ้ฟprefix ไนๆฏsuffix ็ไธไธไฝ |
| 038. Count and Say | O(n * 2^n) | O(n2^n) | Easy | C++ find_if + bind1st |
| 043. Multiply Strings | O(m*n) | O(m+n) | Medium | C++ transform, ๅฟ ้กป้ฝไปไธชไฝๆฐ(ไนๅฐฑๆฏstring็ๆๅไธไฝๅผๅง็ฎ, ๅฆๅcarryๅฏ่ฝไผ่ถ ่ฟ10), back_inserter, ็ธๅฝไบๆ็ งๅๆฅไปๅคดๅฐๅฐพ้กบๅบpush back |
| 058. Length of Last Word | O(n) | O(1) | Easy | C++ find if or find if + bind1st or string find_last_not_of + find_last_of |
| 067. Add Binary | O(n) | O(1) | Easy | string ๅ ๆณ, ่ท415. Add Strings ๅ306. Addictive Number ็ฑปไผผ |
| 068. Text Justification | O(n) | O(1) | Hard | not a hard question, ่ท725. Split Linked List in Parts ็ฑปไผผ |
| 125. Valid Palindrome | O(n) | O(1) | Easy | C++ ่ทณ่ฟ้isalnum็ |
| 151. Reverse Words in a String | O(n) | O(1) | Medium | ๅ reverseๆๆ็, ๅreverseๅไธชๆฏไธช่ฏ, ่ฎฐๅฝๆปๅ ฑlen,ๆๅ็จๆฅๆชๅ, C++ find_first_not_of + find_first_of |
| 165. Compare Version Numbers | O(n) | O(1) | Medium | c++ ็ฎๅฝๅversion1,2็substr็ๆฐ๏ผๅฆๆๅ ถไธญไธไธช็ขฐๅฐ็ปๅฐพ๏ผ่ฎพๅฝๅๆฐไฝ0ใ c, ๅฏไปฅ็จc_str() + strtol; python3 zip(*itertools.zip_longest(*splits, fillvalue=0)) |
| 214. Shortest Palindrome | O(n) | O(n) | Hard | ๐ๅฏไปฅๆๆญค้ขๆขไธ็ง้ฎๆณ: ไปฅindex0ๅผๅงๆ้ฟ็้จๅpalindrome ็้ฟๅบฆ, ้จๅๆ้ฟ็palๅ้ข็ๆไธช+s = ็ญๆก
|
| 242. Valid Anagram | O(n) | O(1) | Easy | ็ปๅ ธ้ข่ฏ้ข |
| 273. Integer to English Words | O(1) | O(1) | Hard | ๆ ่็recursion |
| 306. Addictive Number | O(n^3) | O(n) | Medium | recursion ไปindex0ๅผๅง่ฏๆๆ็digitๅฏ่ฝๆง็ดๅฐๆๅ, ๆฏๅฆๅผๅงๆฏไธไฝ+ไธคไฝ, ่ฟๆฏไธไฝ+ไธคไฝ , ้่ฆไธไธชstring add็help function; python ๅฏไปฅ็จitertools.combination + startswith, ่ท067. Add Binary ๅ415. Add Strings ็ฑปไผผ, ๅชไธ่ฟๅคไธชrecursion |
| 383. Ransom Note | O(n) | O(n) | Easy | Hash map |
| 405. Convert a Number to Hexadecimal | O(n) | O(1) | Easy | ๆๅ็ปๆ้่ฆreverse๏ผๅ ไธบๅ ๆๅ ฅๆๅฐ็๏ผๆณจๆ่ดๆฐ็, -1>>4 = -1, ๆไปฅwhileๅ ไธชๆกไปถ res.length()!=sizeof(int)*2 |
| 415. Add Strings | O(n) | O(1) | Easy | stringๅ ๆณ๏ผ่ท067. Add Binary ๅ306. Addictive Number ็ฑปไผผ |
| 420. Strong Password Checker | O(n) | O(1) | Hard | Brain Storm ่ฏฆ่งC++ code ่งฃ้ |
| 434. Number of Segments in a String | O(n) | O(1) | Easy | ๐, ๆ นๆฎs[i] ๅ s[i-1]ๅคๆญ, or s[i] ๅ s[i+1]ๅคๆญ |
| 443. String Compression | O(n) | O(1) | Easy | two pointer + num reverse |
| 459. Repeated Substring Pattern | O(n) | O(n) | Easy | KMP |
| 468. Validate IP Address | O(1) | O(1) | Medium | ๆณจๆIPv4 ๅIPv6็ๅฎไน(c++ code้), ๅคๆญไธไธชcharๆฏไธๆฏ็ฌฆๅๅๅ ญ่ฟๅถ็จisxdigit(c) |
| 520. Detect Capital | O(1) | O(1) | Easy | C++ count_if; Python istitle()็ๆฏไธๆฏๅชๆ้ฆๅญๆฏๅคงๅ |
| 521. Longest Uncommon Subsequence I | O(min(a, b)) | O(1) | Easy | ้ขๅบ็็ฅ็ป็ ๏ผ้ไฝ ็ฉๅฟ |
| 522. Longest Uncommon Subsequence II | _O(l * n^2) _ | O(1) | Medium | ๐ๆ็ งๅญๆฏ้ฟๅบฆsort, ็ถๅไธไธชไธไธช็str๏ผๆๆฒกๆๅจlistไธญๆsubsequence๏ผๆฒกๆ็่ฏ, return ่ฟไธชstr้ฟๅบฆ,็ดๅฐๅ จ้จsearchๅฎ, return -1 or C++ equal_range + count_if , python ๅฏไปฅiter() |
| 524. Longest Word in Dictionary through Deleting | O((d * l) * logd) | O(1) | Medium | ๆ็ งๅญๆฏ้ฟๅบฆsort,ๅฆๆ้ฟๅบฆไธๆ ท๏ผๆ็ งalphabet sort, ๆพๅฐ็ฌฌไธไธช็ฌฆๅ็ ๐python, max with key, min with key, filter, iter + next with default |
| 539. Minimum Time Difference | O(nlogn) | O(n) | Medium | C++ transform ๆๆๆๆถ้ดๅๅ้, ็ถๅๆminute sort, ็ญๆกๅฐฑๅบ่ชๆๆminute[i+1] - minute[i] or 1440 +minute[0] - minute.back() |
| 541. Reverse String II | O(n) | O(1) | Easy | |
| 551. Student Attendance Record I | O(n) | O(1) | Easy | |
| 556. Next Greater Element III | O(1) | O(1) | Medium | ๅฏไปฅ็จascending stack or ไธคไธชfor loop, ๅฏปๆพi็นๅพๅๆๅไธไธชๆฏi็นๅคง็ๆฐ(ไนๆฏๆฏiๅคง,ๆๆฅ่ฟi็ๆฐ)(index j), swap(s[i], s[j]), ่ฟๆ ทs[i]ๅ้ข็ๆฐๅๅคงๅฐๅฐๆๅบ็, ๆiๅพๅ็ๆฐๅฐendๅ จ้จreverseๅๅๆInt, ๅฐฑๆฏ็ญๆก, ่ท031. Next Permutationๆ่ทฏ็ฑปไผผ |
| 564. Find the Closest Palindrome | O(l) | O(l) | Hard | Brain Storm: ๆๆฅ่ฟ็palๅชๅฏ่ฝ5ไธญ้ไธ, 100..001(l.size()+1), 99..99(l.size()-1), or string็ๅๅ้จๅ +1, +0, -1 ๅ ไธๅๅ้จๅ็reverse(ๅฆๆ่ตทๅง้ฟๅบฆๆฏๅฅๆฐ๏ผreverseไธๅ ๆฌๅๅ้จๅๆๅไธไธช๏ผๅฆๆ้ฟๅบฆๆฏๅถๆฐ๏ผ้ฝๅ ๆฌๅจๅ ) |
| 591. Tag Validator | O(n) | O(n) | Hard | cdata ๅฟ ้กปไปฅ ๅทฒ ]]>็ปๆ, recursion ๆพๆฏไธๆฏvalid tag, valid cdata, valid tagname |
| 647. Palindromic Substrings | O(n) | O(n) | Medium | ๐ manacher(้ฉฌๆ่ฝฆ็ฎๆณ), ๅจsnewไธญ p[i]่กจ็คบไปฅidไธบไธญๅฟๆ้ฟๅๆ๏ผๅฐi็น๏ผres += p[i] /2 |
| 648. Replace Words | O(n) | O(t) | Medium | ๐ Trie; python ๅฏไปฅ็จreduce + dict.__getitem__ |
| 657. Judge Route Circle | O(n) | O(1) | Easy | |
| 678. Valid Parenthesis String | O(n) | O(1) | Medium | ๐Three Solutions
|
| 680. Valid Palindrome II | O(n) | O(1) | Easy | ๐ไธคไธชpointer, ๆฃๆฅs[i] == s[j]?, ้ๅฐไธ็ญๆถ๏ผๅ็s[i+1, j], or s[i, j-1]ๆฏไธๆฏpal |
| 686. Repeated String Match | O(n+m) | O(n) | Easy | ๐
|
| 696. Count Binary Substrings | O(n) | O(1) | Easy | manacher(้ฉฌๆ่ฝฆ)็ฎๆณ็ๅๅฝข |
| 720. Longest Word in Dictionary | O(n) | O(t) | Easy | Trie or ๅ ๆ้ฟๅบฆsort, ้ฟๅบฆ่ถ็ญ, ๆๅ้ข, loop word, loop s[i][0,len), ็ๆฏไธๆฏๆฏไธชsubstr้ฝๅจ๏ผ้ฝๅจ่ฏinsert to hashset & update result |
| 722. Remove Comments | O(n) | O(k) | Medium | |
| 791. Custom Sort String | O(n) | O(k) | Medium | ๅฏไปฅๅฝ็ปๅ
ธ้ข่ฏ้ข, ไธ็ง่งฃๆณ:
|
| 796. Rotate String | O(n) | O(1) | Easy | ๐ไธค็งkmp็่งฃ,
|
| 804. Unique Morse Code Words | O(n) | O(n) | Easy | Easy one unordered_set |
| 806.Number of Lines To Write String | O(n) | O(1) | Easy | Easy one but stupid question description |
| 809. Expressive Words | O(n+s) | O(1) | Medium | Two pointer: ๅฆๆword[i]!=S[j] ็ๆถๅ๏ผ ็S็j-1, j, j+1ๆฏไธๆฏ่ฟ็ปญๆฏไธไธช๏ผ่ฅไธๆฏ๏ผๅ็่ฟๅปๆฏไธๆฏ่ฟ็ปญไธไธช๏ผ่ฅไธๆฏ๏ผbreak |
| 816. Ambiguous Coordinates | O(n^3) | O(n) | Medium | ๐้ๆฉๅฐๆฐ็น็ๅ ณ้ฎๆฏ ไธ่ฝๅทฆ้ขไฝ0๏ผ ๅณ้ข็ปๆไนๆฏ0๏ผๆฏๅฆ00.1230ไธๅฏไปฅ,ไฝๆฏๅณไฝฟๅทฆ้ข็ญไบ0๏ผ ๅณ้ขๆๅไนไธๅฏไปฅๆฏ0 |
| 819. Most Common Word | O(n+m) | O(m+n) | Easy | |
| 820. Short Encoding of Words | O(n) | O(t) | Medium |
|
| 824. Goat Latin | O(n + w^2) | O(l) | Easy | stringstream ไฝไธบstring output |
| 831. Masking Personal Information | O(1) | O(1) | Easy | C++ transform ๆๆๆๅญๆฏ้ฝๅฐๅ, s[0] ๅๆstring ๅฏไปฅ็จ s.substr(0,1) or string(1,S[0]) |
| 833. Find And Replace in String | O(m+n) | O(n) | Medium | ๅ sort indexes,็ถๅไปๅๅพๅloop S,่ฟๆ ทๅฏไปฅไฟๆSๅ้ข็indexไธๅ, python ๅฏไปฅ็จzip + startswith |
| 839. Similar String Groups | O(n^2 * l) | O(n) | Easy | ๐ Union Find Disjoint Set with Rank Heuristic, string ๆๅจไฝ็ฝฎไธบindex |
| 848. Shifting Letters | O(n) | O(1) | Medium | ๅ ็ๆถๅๅๆถ%26, ๅฐๅฟoverflow |
| 859. Buddy Strings | O(n) | O(1) | Easy | ๅคๆญๆกไปถ: 1.้ฟๅบฆไธไธๆ ท๏ผfalse๏ผ2. ๅฆๆa == b๏ผๆๆฒกๆ้ๅค็ๅญๆฏ๏ผๆ็่ฏtrue, ๆฒกๆfalse, 3, ๅฆๆไธไธๆ ท็ไฝ็ฝฎไธชๆฐไธ็ญไบ2, ๆ่ a[diff[0]]!=b[diff[1]] or a[diff[1]]!=a[diff[1]] ่ฟๅfalse, ๅฆๅๆฏtrue |
| 1374 Generate a String With Characters That Have Odd Count | O(n) | O(1) | Easy | โ |
| 1392. Longest Happy Prefix | O(n) | O(n) | Hard | KMP, Rolling Hash |
| 1408. String Matching in an Array | O(n) | O(n) | Easy | KMP, Rolling Hash |
| 1410. HTML Entity Parser | O(n) | O(t) | Medium | |
| 1417. Reformat The String | O(n) | O(1) | Easy | |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| summary |
|---|
reference reference2
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 136. Single Number | O(n) | O(1) | Easy | ็จxor ^, Python Reduce one line |
| 137. Single Number II | O(n) | O(1) | Medium | ๐
|
| 190. Reverse Bits | O(1) | O(1) | Easy | ไธไฝไธไฝreverse bit, resๆฏๆฌกๅๅทฆ็งปๅจไธไฝ๏ผnๅๅณ็งปๅจไธไฝ |
| 191. Number of 1 Bits | O(n) | O(1) | Easy | n = n & (n-1); |
| 201. Bitwise AND of Numbers Range | O(1) | O(1) | Medium | ไธไฝไธไฝๆฏ่พdigit๏ผ็ดๅฐ็งปๅจkไฝm=n, ้ฃไนๆญคๆถ็digitๆฏbitwise and็็ปๆ, res = m<<k |
| 231. Power of Two | O(1) | O(1) | Easy | n = n & (n-1); |
| 260. Single Number III | O(n) | O(1) | Medium | ๐ไธคไธชpass,็ฌฌไธไธชpass, ้่ฟXor้่ฆๅบๅa ๅ b็ๆฐ c(ๆฏaไธbๅณ้ข็ฌฌไธไฝไธไธๆ ท็ๆฐ), ็ฌฌไบๆฌกpass, ้่ฟc&nums[i]ๅคๆญๅxor, ๆพๅฐaๅb (binary ่ดๆฐ) |
| 268. Missing Number | O(n) | O(1) | Medium | Math, Swap, Xor |
| 318. Maximum Product of Word Lengths | O(n^2) | O(n) | Medium | ๐ๅฏไปฅ็จbitๆฅๅคๆญไธคไธชstringๆฏไธๆฏๆ้ๅ็ๅญๆฏ, ็จๆฐๅญ่กจ็คบstring, aๆฏ็ฌฌไธไฝ่ขซset๏ผzๆฏ็ฌฌ26ไฝ่ขซset, |
| 342. Power of Four | O(1) | O(1) | Easy | 4^n = (3+1)^n, ้คไบๅคๆญ(n&n-1) , ่ฟ่ฆๅคๆญn-1 ๆฏไธๆฏๅฏไปฅๆด้ค3 |
| 371. Sum of Two Integers | O(1) | O(1) | Easy | ๏ผa&b)<<1 ่กจ็คบ้่ฆ็ธๅ ่ฟไฝ็๏ผไธคไธช1็ธๅ ๏ผ, a ^ b ่กจ็คบ็ธๅ ไธ่ฟไฝ๏ผไฟ็ๅไธช1๏ผ |
| 389. Find the Difference | O(1) | O(1) | Easy | ๐ๆพไธคไธชstringๅฏไธไธๅไธๅ็charๅฏไปฅ้่ฟ xor |
| 393. UTF-8 Validation | O(n) | O(1) | Easy | ็จcountๅคๆญๆฏไธๆฏ่ตท็น, count==0 ๆฏ่ตท็น |
| 421. Maximum XOR of Two Numbers in an Array | O(nlogk) | O(n) | Medium | ๐
|
| 461. Hamming Distance | O(1) | O(1) | Easy | ๅคๆญๆๅคๅฐbit, ไธ191. Number of 1 Bitsๅ 231. Power of Two็ฑปไผผ |
| 462 Minimum Moves to Equal Array Elements II | O(nlogn) | O(1) | Medium | ๐Meeting point, ๅ sort๏ผ็ถๅ้ไธช็จๆๅคงๅๅปๆๅฐ, e.g [3,6,9], ไธ็ฎกไธญ้ด็นๅจๅช๏ผ้ฝ่ฆ็ฃจๅนณ9-3=6็ๅทฎ่ท |
| 476. Number Complement | O(1) | O(1) | Easy | |
| 477. Total Hamming Distance | O(nlogk) | O(1) | Easy | ็ฑ็ฌฌ32ไฝๅฐ็ฌฌ0ไฝ๏ผloopๆฏไธชbit๏ผๆฐๅฝๅbitไฝไธบ1็ไธชๆฐไธบbitcount, ็ปๆ res+= bitcount*(size-countsize), ไธ421. Maximum XOR of Two Numbers in an Array็ฑปไผผ |
| 645. Set Mismatch | O(n) | O(1) | Easy |
|
| 693. Binary Number with Alternating Bits | O(1) | O(1) | Easy | ๐ |
| 762. Prime Number of Set Bits in Binary Representation | O(R-L) | O(1) | Easy | loop[L,R],ๆฐๆฏไธชๆฐๅคๅฐไธชbit๏ผๅ ไธบlog2(10^6) < 16, ไบๅ ๆๆๆ็primeๅญๅฐhash set้้ข, ็็ฐๅจbitๆฐๆฏไธๆฏ่ดจๆฐ๏ผif so res++, ่ฟๅฏไปฅ็จ __builtin_popcountl(n); bitset<32>(n).count() |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย | C++ 0b่กจ็คบbinary number๏ผๆฏๅฆ0b10 = 2, 0b111 = 7 python 0b่กจ็คบbinary number๏ผๆฏๅฆ0b10 = 2, 0b111 = 7
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 001 Two Sum | O(n) | O(n) | Easy | |
| 003. Longest Substring Without Repeating Characters | O(n) | O(n) | Medium | |
| 030. Substring with Concatenation of All Words | O((m+n)*k) | O(n*k) | Hard | ๐k = word[0]้ฟๅบฆ, n = ๆดไธชwords้ฟๅบฆ, m = S็้ฟๅบฆใๆๅฟซ็่งฃๆฏไธคไธชmap, map1่ฎฐๅฝwords็ๆฏไธชstring, |
| 036. Valid Sudoku | O(9*9) | O(9) | Medium | ๐ ็จbitๆฏ่พๅฟซ๏ผๆฏๅฆiๅจๆจช็็ฌฌ2่กๅบ็ฐ, row[2] |
| 049. Group Anagrams | O(n * glogg) | O(n) | Medium | ็ปๅ ธ ้ข่ฏ้ข, python listไธ่ฝไฝไธบๅญๅ ธ็key,ไฝๆฏtupleๅฏไปฅ |
| 076. Minimum Window Substring | O(n) | O(k) | Hard | ๐sliding windows, ๆญค้ขๆฒกๆ็ชๅฃ็size๏ผ่ฆๅปๆพๆๅฐ็size๏ผๅ ณ้ฎๆฏๅฆไฝ็กฎๅฎwindow valid๏ผ่ฎฐๅฝๆฏๆฌกๆปๅฐcur charไนๅจTไธญๅบ็ฐ็ไธชๆฐ๏ผๅฝไธชๆฐๆปก่ถณT.size(),่ฏๆwindow valid๏ผ็ถๅ้ๆญฅ็ผฉๅฐstartไธi็่ท็ฆป๏ผๆพๆๅฐ็น |
| 149. Max Points on a Line | O(n^2) | O(n) | Hard | ๆฏๅฐไธ็น๏ผ็ฎ่ทๅซ็็น็ๆ็๏ผๆณจๆ1. ้ๅ็็น๏ผ2.ๆ็ๆฒกๆ็ๅฎไน็็น, ๅจๆฏไธ็น้ฝ้ๆฐๅปบไธไธชhashmap |
| 187. Repeated DNA Sequences | O(n) | O(n) | Medium | ๐ rolling hash (rabin-karp),
|
| 202. Happy Number | O(k) | O(k) | Easy | ่ฆไนๆฏhappy number๏ผ่ฆไน่ฝฌๅ่ฟ็จ้ทๅ ฅๅพช็ฏ |
| 204. Count Primes | O(n) | O(n) | Easy | countไปๅฐๅพๅคงๅeliminate๏ผๆณจๆ่ฆๅฐฝๅฏ่ฝefficient |
| 205. Isomorphic Strings | O(n) | O(1) | Easy | ๅฏไปฅ่ฎฐๅฝ็ธๅไฝ็ฝฎๅญๆฏๅบ็ฐ็ไธไธไฝ๏ผๆ่ ๆs,tๅญๆฏ็ธไบๅ ณ่่ตทๆฅ, python ๅฏไปฅ็จfind+map or zip+set |
| 217. Contains Duplicate | O(n) | O(n) | Easy | easy one, ๅฏไปฅ็จsort + unique |
| 219. Contains Duplicate II | O(n) | O(n) | Easy | easy one |
| 290. Word Pattern | O(n) | O(n) | Easy | ๆ่ทฏๅ205. Isomorphic Strings ไธๆ ท |
| 299. Bulls and Cows | O(n) | O(1) | Easy | One pass: ๅฆๆguess[i] ๅ secret[i]ไธๆ ท, bull++, ไธไธๆ ท๏ผ++m[sec[i]], --m[guess[i]] python ๅฏไปฅ็จไธคไธชcollectons.Counter็ธๅ, ๅพๅฐ้ๅ็set |
| 336. Palindrome Pairs | O(n * k^2) | O(n*k) | Hard | ๐trie |
| 387. First Unique Character in a String | O(n) | O(n) | Easy | ้่ฆ two pass |
| 388. Longest Absolute File Path | O(n) | O(d) | Medium | map่ฎฐๅฝๆฏไธๅฑ็ฐๆ็้ฟๅบฆ,ๅฐๆฐ็ๆ่ ๅๆฅไธๅฑ๏ผๆดๆฐmap, resๆฏmax(mapไธญๅซๆโ.โ็ไธๅฑ), ็จๅฐstring::find, string::find_first_not_of, std::find |
| 409. Longest Palindrome | O(n) | O(1) | Easy | ๅฏไปฅ็จstd::count, ๆ่ ๅฏไปฅๆฅๅflip map, ๅฝmapไฝtrue +2 |
| 424. Longest Repeating Character Replacement | O(n) | O(1) | Medium | ๐sliding window: ่ฎฐๅฝwindow็ๅๅง็น, ๅฆๆๅฝๅ้ฟๅบฆ - ๆๅคงcount > k, ++start(ไฟๆwindows็ๆๅคง้ฟๅบฆ), ๅฆๆๆปก่ถณ๏ผstartไธๅ๏ผ็ปๆๆฏs.size()-start |
| 438. Find All Anagrams in a String | O(n) | O(1) | Easy | sliding window: ่ท567. Permutation in Stringๆ่ทฏไธๆ ท
|
| 447. Number of Boomerangs | O(n^2) | O(n) | Easy | ๅฏไปฅ็จhypot |
| 454. 4Sum II | O(n^2) | O(n) | Medium | ๅฏไปฅๆ4sum็ๆtwo sum, ๆA+B็ๅ็ปๅฎ๏ผๆC+D็ๅ็ปๅฎ๏ผ็-C-DๆฏไธๆฏๅจA+B็map้ |
| 473. Matchsticks to Square | O(n * s * 2^n) | O(n * (2^n + s)) | Medium | DFS or Bit Mask |
| 523. Continuous Subarray Sum | O(n) | O(k) | Medium | ๐ๆฑๅผๅงๆฐๅฐๆๆi็ๅ็ไฝๆฐ๏ผๅฆๆ็ฐๅจ่ฟไธช็ไฝๆฐไนๅ้ๅฐ่ฟ๏ผ่กจ็คบ๏ผไธคไธชๆฐไน้ดๆๆฐ็ๅๆญฃๅฅฝๆด้คk |
| 532. K-diff Pairs in an Array | O(n) | O(n) | Easy | ๐one pass่งฃ: ไธคไธชhashset, lookup ๅres, ๆพ็ๆถๅๆขๅไธๆฐๅๅไธๆฐ, ไธบไบ้ฟๅ ้ๅค, set(res)ๅชpushไธ้,็ปๆๅฐฑๆฏres size |
| 554. Brick Wall | O(n) | O(m) | Meidum | ็ธๅฝไบๆฑๆๅค็ป่ฟ็ ๅคด็ผ็ผ |
| 560. Subarray Sum Equals K | O(n) | O(k) | Medium | ๐็จhashmap่ฎฐๅฝๆฏ็น็rolling sum(0,i)๏ผ ้ฃไนๅช้่ฆๆพ(0,i)็sum - kๅจไธๅจmapไธญ๏ผๅจ็่ฏ ่กจ็คบๅญๅจไธ็น[0,j] + k = (0,i)็sum๏ผ res += map[sum-k] (ๅฏ่ฝไธไธชsumๅบ็ฐๅพๅค้) |
| 561. Array Partition I | O(n) | O(n) | Easy | Sort or Bucket Sort |
| 575. Distribute Candies | O(n) | O(n) | Easy | ๅฏนๆฏset็้ฟๅบฆๅcandies.size()/2็้ฟๅบฆ, C++ๅฏไปฅ็จbitset |
| 594. Longest Harmonious Subsequence | O(n) | O(n) | Easy | |
| 599. Minimum Index Sum of Two Lists | O((m + n) * l) | O(m * l) | Easy | |
| 609. Find Duplicate File in System | O(n * k) | O(n * k) | Medium | |
| 721. Accounts Merge | O(nlogn) | O(n) | Medium | ๐ Union Find, ไธ่ฝ็จ็ฎๅ็hash table ๆพparent, ๆฏๅฆ (1@com, 2@com), (3@com, 4@com), (4@com, 2@com), ไธ็จUnion findๅๆไธค็ป |
| 748. Shortest Completing Word | O(n) | O(1) | Medium | |
| 771. Jewels and Stones | O(n+m) | O(n) | Easy | |
| 811. Subdomain Visit Count | O(n) | O(n) | Easy | |
| 822. Card Flipping Game | O(n) | O(n) | Medium | ๅ ๆfront[i]ๅend[i] ไธๆ ท็ๆๅ ฅๅฐhash set, ๅloop front & end, ้ๅไธๅจhash setไธญๆๅฐ็ |
| 825. Friends Of Appropriate Ages | O(n+k^2) | O(k) | Medium | ็จhash mapๅญageๅcount, loopไธคๅฑhashmap, ๅคๆญๅ ๅฑๅๅคๅฑkeyๆฏๅฆๆปก่ถณๆกไปถ, ๆปก่ถณ็่ฏๆดๆฐ็ปๆ |
| 1418 Display Table of Food Orders in a Restaurant | O(n + tlogt + flogf) | O(n) | Medium | โ๏ธC++ transform |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| summary |
|---|
sliding windows: windows้ฝๆฏ็ไปฅๅฝๅๅญๆฏ็ปๅฐพ็window. ๆฏ่พๅฏน่ฑกs1, ่ขซๆฏ่พๅฏน่ฑกs2
|
// 438. Find All Anagrams in a String
//s2: "cbaebabacd" s1: "abc"
//Output: 0, 6]
//ๅบๅฎwindows้ฟๅบฆ
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
vector<int>map(26,0);
for(auto i: s1)
map[i-'a']++;
int len = s1.size(), count = s1.size();
vector<int>res;
for(int i = 0; i<s2.size();i++){
if(map[s2[i]-'a']-->0) count--;
if(count == 0) res.push_back(i-len+1);
if(i>=len-1){
if(++map[s2[i-len+1]-'a'] > 0) count++;
}
}
return res;
}
};
//ไธๅบๅฎwindows้ฟๅบฆ, ๆนๆณไธ:
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
vector<int>map(26,0);
for(auto i: s1)
map[i-'a']++;
int len = s1.size(), left = 0;
vector<int>res;
for(int i = 0; i<s2.size();i++){
map[s2[i]-'a']--;
if(map[s2[i] - 'a'] <0)
while(left<= i && map[s2[i]-'a'] < 0) map[s2[left++]-'a']++;
/* or
//correct
while( mp[s2[left]]++ >= 0 )
++left;
++left;
//wrong: ๆฏๅฆ ab: eabc, left ไผไธ็ดๅๅจ0(e)
while( mp[s2[left]] >= 0 )
mp[s2[left++]]++
*/
if(i-left+1 == len){
res.push_back(left);
}
}
return res;
}
};
//ไธๅบๅฎwindows้ฟๅบฆ ๆนๆณไบ:
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
vector<int>map(26,0);
for(auto i: s1)
map[i-'a']++;
int len = s1.size(), left = 0;
vector<int>res;
for(int i = 0; i<s2.size();i++){
map[s2[i]-'a']--;
if(map[s2[i] - 'a'] <0)
while(map[s2[left++]-'a']++ >= 0);
//cout<<i <<" left "<<left<<endl;
if(i-left+1 == len){
res.push_back(left);
}
}
return res;
}
};
/*
"cbaebabacd"
"abc"
DEBUG stdout
0 left 0
1 left 0
2 left 0
3 left 4
4 left 4
5 left 4
6 left 5
7 left 6
8 left 6
9 left 10
*/
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 567. Permutation in String | O(n) | O(1) | Medium | ๐sliding Window(้ฟๅบฆไธบlen(s1)), ๆฏๆฌก็งปๅจๆก,vectorๅๅปๆฐๆฅ็๏ผๅ ไธๅๅpass็๏ผ็ดๅฐl้ฟๅบฆไธบ0 |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 020. Valid Parentheses | O(n) | O(n) | Easy | โๆณจๆreturn true if stack is empty |
| 032. Longest Valid Parentheses | O(1) | O(n) | Hard | ๐
|
| 071. Simplify Path | O(n) | O(n) | Medium | โ๏ธ getlineๅฏไปฅๅฝๅstack, ้ๅฐ".." stack pop; vectorๅฏไปฅ็จไฝstack |
| 084. Largest Rectangle in Histogram | O(n) | O(n) | Hard | ๐
|
| 085. Maximal Rectangle | O(n*m) | O(m) | Hard | ๐
|
| 101. Symmetric Tree | O(n) | O(h) | Easy | โ ๆณจ: iterative stack push ้กบๅบ |
| 150. Evaluate Reverse Polish Notation | O(n) | O(n) | Medium | โ๏ธ Python Lambda Function in dictionary ๐ C++ recursive solution |
| 155. Min Stack | O(n) | O(1) | Easy | ๐ Descending Stack: ไธคไธชstack,ไธไธช็จๆฅๆพๆญฃๅธธ็้กบๅบ๏ผๅฆไธไธชไฝไธบmin |
| 173. Binary Search Tree Iterator | O(1) | O(h) | Medium | 307. Range Sum Query - Mutable ้ป่พ็ฑปไผผ, ไธ่ฆๅ ๅ จ้จ่ตฐๅฎ |
| 232. Implement Queue using Stacks | O(1), amortized | O(n) | Easy | ๐ไธคไธชstack in & out, in็จๆฅpush, top: ๅๅฆoutไธบ็ฉบ๏ผdump in to out |
| 224. Basic Calculator | O(n) | O(n) | Hard | โ็จsign=1่ฎฐๅฝ+, -1่ฎฐๅฝๅ, ็ขฐๅฐnumไนไปฅres,'('res,sign push่ฟstack, ')'ๅ ไนไปฅstack็top(ๆฏsign),ๅๅ ไธstack็top(signไนๅ็res) |
| 227. Basic Calculator II | O(n) | O(n) | Medium | โ ็จsign=1่ฎฐๅฝ+, -1่ฎฐๅฝๅ, sign = 2 ่ฎฐๅฝ*๏ผ 3่ฎฐๅฝ้ค, ไธไธไธชsignๆฏไนๆ้ค๏ผๅ ่ฟ่กoperation |
| 331. Verify Preorder Serialization of a Binary Tree | O(n) | O(n) | Medium | ๐๐โ๏ธstringstream + getline
|
| 341. Flatten Nested List Iterator | O(n) | O(h) | Medium | ๐๐stack + recursionไปๆๅๅพๅloop, queueไปๅๅพๅloop, โ๏ธโ๏ธC++/Python Iterator, ่ฆๅญiterator, ไธ่ฝๅญvector, ๅ ไธบๅญvector memoryไผๅพๅคง |
| 385. Mini Parser | O(n) | O(h) | Medium | ้ๅฐ',' ']' ๆไนๅ็integer add๏ผ ๆฏๅฆ[-1], [123,456], ้ๅฐ']',ๆ็ฐๅจ่ฟไธชnested listๅ ๅ ฅไธไธชnested list |
| 394. Decode String | O(n) | O(h) | Medium | ๐ๅฏไปฅ็็recursive ็่งฃ, ็จๅบ่ฎพ่ฎก: ๆไน่ฎพ่ฎกไธไธชๅฅฝ็stack, ็ฑปไผผ726. Number of Atoms
|
| 456. 132 Pattern | O(n) | O(h) | Medium | ๐ ๐ ๅฏปๆพ s1 < s3 < s2๏ผไปๅๅๅ๏ผDescending stack, ้พ็น: ็่งฃstack่ฎฉs2 ้ๆธๅๅคง, ไฝs3ๅฏๅขไนๅฏๅ, ๅ ไธบs2ๅๅฐๅๅฐฑreturn trueไบ |
| 636. Exclusive Time of Functions | O(n) | O(n) | Medium | ๐stack ๅญ็ๆฏไธไธชjob็id |
| 682. Baseball Game | O(n) | O(n) | Easy | โbad problem description |
| 726. Number of Atoms | O(n^2) | O(n) | Hard | ็ฑปไผผ 394. Decode String |
| 735. Asteroid Collision | O(n) | O(n) | Medium | ๐ ็ขฐๆๅ็ๅช่ฝๆฏๆฐๆฅ็ๅฐไบ0๏ผstack top > 0 |
| 736. Parse Lisp Expression | O(n) | O(n) | Hard | โstack้่ฆไธคไธช๏ผไธไธชๆฏๅญstring dict(็จๆฅๅจๅญlet็ๅญๅ ธ), ไธไธชๅญstring vector(็จๆฅๅจๅญไธไธชstring็split), ้ๅฐ'(', ๅฆๆไนๅๆฏlet, ๅ ๅญmap, ็ถๅpush่ฟไธคไธชstack, string vectorๆธ ็ฉบ๏ผๅญๅ ธไธๆธ ็ฉบ ใ ้ๅฐ')', ็ฎๅฝๅ็, ๆ็ปๆpushๅฐไธไธชstring(stkstring.top()) ็็ปๅฐพ, popไธคไธชstack |
| 739. Daily Temperatures | O(n) | O(n) | Medium | ๐ Ascending/Descending stack, ๅฏไปฅๆญฃๅไนๅฏไปฅๅๅ |
| 0901. Online Stock Span | O(n) | O(n) | Medium | |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย | Ascending & Descending Stack ๆ็ ง container็้กบๅบ่ฟ่กๆๅบ |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 002. Add Two Numbers | O(n) | O(1) | Medium | |
| 021. Merge Two Sorted Lists | O(n) | O(1) | Easy | |
| 023. Merge k Sorted Lists | O(nklogk) | O(1) | Hard | Heap, Divide Conquer, ๆณจ: ไธ่ฝ็จไธ็ด็จ0ไฝไธบl ๅrๆฏ๏ผ่ฟๆ ท็่ฏ๏ผl็sizeไผๅขๅ ็ๅพๅฟซ๏ผๅฐๆๅl sizeๅฟซๆไฝnkไบ |
| 024. Swap Nodes in Pairs | O(n) | O(1) | Easy | ๅปบdummy, ๆๅๅพๅ็ฌฌไบไธชไธบnextnext๏ผๆญ็ฌฌไบ๏ผไธ้พ, nextnextๅๆฅไธๅฝๅ็next, ๆnextnextๆฅๅฐๅฝๅ็next, ptๅพๅ่ตฐไธคๆญฅ |
| 025. Reverse Nodes in k-Group | O(n) | O(1) | Hard | ็ฑปไผผ206 Reverse Linked List |
| 061. Rotate List | O(n) | O(1) | Medium | |
| 082. Remove Duplicates from Sorted List II | O(n) | O(1) | Medium | |
| 083. Remove Duplicates from Sorted List | O(n) | O(1) | Easy | ไธ่ฝ็จrecusion, recursion็่ฏไผ็จpass nๅlinked list๏ผ็จO(n)space, iterative่งฃspaceๅช็จO(1),treeๅฏไปฅ็จrecursionๅๅ ๆฏๅฎ็stack spaceๆฏO(logn) |
| 138. Copy List with Random Pointer | O(n) | O(1) | Medium | 1. ๅ
ๆๆฏไธชnodeๅคๅถไธไธช๏ผๆๅคๅถ็่ดดๅจ่ขซๅคๅถ็ๅ้ข 2. loop node(็ฐๅจ้ฟๅบฆๆฏ2n), ๆcur->next->random = cur->random->next๏ผๅ ไธบcur->random->nextๆฏๅคๅถcur->random่ฟๆฅ็ 3. ๆๅ็ปๆๅฐฑๆฏๆๆฏไธชๅถๆฐไฝ็node่ฟๆฅ่ตทๆฅ๏ผๅๆถ่ฆๆถ้คๅถๆฐ็node(้ฟๅบฆ็ฑ2nๅๅn)๏ผๅฆๅ็ปๆๆฏไฟฎๆนไบๅๆฅ็node |
| 147. Insertion Sort List | O(n^2) | O(1) | Medium | Sort |
| 148. Sort List | O(nlogn) | O(logn) | Medium | Sort
|
| 160. Intersection of Two Linked Lists | O(n+m) | O(1) | Easy | ๅฉ็จ็ๆฏ lA + lB_1 = lA_1 + lB (lenA + Bไบค็นๅ็้ฟๅบฆ = lenB + Aไบค็นๅ็้ฟๅบฆ), pA๏ผpB ๆฏๆฌก้ฝๅ่ฟไธๆญฅ๏ผpAๅฐend,pA่ฎพไธบBhead, pBๅฐend,pB่ฎพไธบAend, ่ฟ็งๅฐพๅฏนๅคดๅชๆขไธๆฌก๏ผ็ฌฌไบๆฌกpA ๆ่ pBๅฐend ่ฟๅNULL(ๅฐฑๆฏๆฒกๆไบค็น) |
| 203. Remove Linked List Elements | O(n) | O(1) | Easy | |
| 206. Reverse Linked List | O(n) | O(1) | Easy | |
| 234. Palindrome Linked List | O(n) | O(1) | Easy | revese listๅ้ข้จๅ๏ผ็ถๅreverseไนๅ๏ผ้ไธชๅฏนๆฏๅๅ้จๅๆฏๅฆ็ญไบๅๅ้จๅ็ๅผ |
| 237. Delete Node in a Linked List | O(n) | O(1) | Easy | ๆnode->next็valๆๅฐnode val็ถๅdelete node->next |
| 328. Odd Even Linked List | O(n) | O(1) | Medium |
|
| 445. Add Two Numbers II | O(n+m) | O(m+n) | Medium | ็จไธคไธชstack,ๆๆฏไธชlistๅผpush ่ฟstack๏ผๆๅpush่ฟ็ๅ ็ฎ |
| 725. Split Linked List in Parts | O(n) | O(1) | Medium | ๆฏๆฌกๅ่ฟๅฐๆญคๆฌกpush่ฟvector็ๆๅไธไฝ, ็ถๅๆญ้พ, ็ฌฌiไธชvector้ฟๅบฆไธบ n//k + (i< n%k) |
| 817. Linked List Components | O(n+m) | O(m) | Medium | ๆvector่ฝฌๅๆunordered_set, ็ถๅๅคๆญๆฏไธชval,ๆฏไธๆฏๅจunordered_set้้ข |
| LinkedList ๅฝhead, cur ๆๅๅไธ็น, cur = cur->next; | head ไธไผๆนๅ, ไฝๆฏๅฝcurๅจheadไนๅ๏ผheadๅ ๅซcur, cur = cur->next, headไผ่ทณ่ฟcur่ฟ็น | |||
| two pointer 1.whiLe(fast->next && fast->Next->next) ๆฏๆพไธญ็น, ๆฏๅฆ1-2-3-4-5-6๏ผslowๆๅ็ญไบ3 2.whiLe(fast && fast->Next) ๆฏๆพไธญๅไธ็น,ๆฏๅฆ1-2-3-4-5-6๏ผslowๆๅ็ญไบ4, 1-2-3-4-5 ๆๅๆฏ3 |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 239. Sliding Window Maximum | O(n) | O(k) | Hard | ๐ Monoqueue using Deque
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
|
||||
| 264. Ugly Number II | O(n) | O(1) | Medium | ๐๐
๐
|
| 295. Find Median from Data Stream | O(nlogn) | O(1) | Medium | ่ฝๆฏhard, ้ป่พ็ฎๅ, ไธคไธชheap, minheap, maxheap, โ๏ธๅฏไปฅ็็python heapq็จๆณ heappushpop |
| 313. Super Ugly Number | O(n*k) | O(n+k) | Medium | ็ฑปไผผ 264. Ugly Number II |
| 373. Find K Pairs with Smallest Sums | O(k * log(min(n, m, k))) | O(min(n, m, k)) | Medium | ๐ๆณจ: ไธ็จhashset, ๅฏไธ้ๅคpush ่ฟheap ๐ ไธ่ฝ็จtwo pointer, ๆฏๅฆ [1,7], [2,6], ็ปๆๆฏ[1,2],[1,6],[2,7], two pointer็ป็ๆฏ[1,2],[1,6],[6,7] โ๏ธ: python itertools.product, itertools.islice O(k) solution |
| 378. Kth Smallest Element in a Sorted Matrix | O(k * log(min(n, m, k))) | O(min(n, m, k)) | Medium | Binary Search, Heap, ZigZag Search |
| 407. Trapping Rain Water II | O(m * n * (logm + logn)) | O(m*n) | Hard | ๐๐
|
| 632. Smallest Range Covering Elements from K Lists | O(nklogk) | O(k) | Hard | ๐๐
|
| 846. Hand of Straights | O(nlogn) | O(n) | Medium | ๐
|
| 846. Hand of Straights | O(nlogn) | O(n) | Hard | |
| 973. K Closest Points to Origin | O(n) average | O(1) | Easy | โ๏ธQuick-Select |
| 1046. Last Stone Weight | O(nlogn) | O(n) | Easy | |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
Two pointer ็จไบ
- detect cycle
- sorted arrayๆฏๅคงๅฐ,ไธไธชarrayไธไธชpointer
- linked listๆพๅฐmiddle point
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 019. Remove Nth Node From End of List | O(n) | O(1) | Medium | ๐two pointer, listๆป้ฟl, ้่ฆremove็indexๆฏl-n, slow่ฆๅ่ฟๅฐl-n-1, ๆไปฅๅ ๅ่ฟnไธช๏ผๅๅ่ฟๅฐๅฐพ้จๅฐฑๆฏl-n-1 |
| 086. Partition List | O(n) | O(1) | Medium | ๐
|
| 141. Linked List Cycle | O(n) | O(1) | Easy | โ |
| 142. Linked List Cycle II | O(n) | O(1) | Medium | ๐ๅ ทไฝๆฐๅญฆ่งฃ้, ็ฑปไผผ287. Find the Duplicate Number |
| 143. Reorder List | O(n) | O(1) | Medium | ๐๐ ็จfast & slowๅ ๆพๅฐmedium็็น๏ผslowๅฐ็ปๅฐพๆๆ็็นreverse, ็ถๅp1 = head, p2 = middleๅไธ็น๏ผไธไธชp1, ไธไธชp2 ๆ่ฟpointer๏ผๅฐฑๆฏ็ปๆ |
| 167.Two Sum II - Input array is sorted | O(n) | O(1) | Easy | โ two pointer, ไธไธชไปๅผๅงไฝ็ฝฎ๏ผไธไธชไปๆซๅฐพ็ไฝ็ฝฎ |
| 283. Move Zeroes | O(n) | O(1) | Easy | โ ่ฎฐๅฝswapๅ็ฌฌไธไธช0ไฝ็ฝฎ |
| 287. Find the Duplicate Number | O(n) | O(1) | Easy | ๐๐
็ฑปไผผ142. Linked List Cycle II ,ๆduplicateไธๅฎไผๆcycle, ้พ็น: ๆพ่ตท็น
|
| 344. Reverse String | O(n) | O(1) | Easy | ๐bitๆฅ่ฟ่กswap |
| 349. Intersection of Two Arrays | O(n+m) | O(min(m, n)) | Easy |
|
| 350.Intersection of Two Arrays II | O(n+m) | O(1) | Easy | โ
|
| 457. Circular Array Loop | O(n) | O(1) | Medium | โarray loopๅฟ ้กปๆฏๅๅ็, ๆฏๅฆ1->2, 2->1 ไธ็ฎๆฏloop๏ผๅพช็ฏarrayๆฏๆฌกไธคไธชpointerๆฃๆฅๆๆฒกๆloop,ๅฆๆๆฒกๆloop,ๆ่ฟๆฌกๆๆ่ตฐ่ฟ็็น้ฝๆ ๆ0,ไธๆฌกไธ็จๅ่ตฐไบ, ็ฑปไผผ141. Linked List Cycle |
| 611. Valid Triangle Number | O(n^2) | O(1) | Medium | ๐ (ๆ ๆณ่พพๅฐO(n))๏ผๅ sort็ถๅไธคไธชpointer,ๆฏไธไธช้ฝๆๅไธไธช่พน, |
| 777. Swap Adjacent in LR String | O(n) | O(1) | Medium | ๐ ้พ็นๆฏ: ๅฏปๆพleft ๅ right. Rๆฏๅๅ่ตฐ๏ผLๆฏๅๅ่ตฐ๏ผswap R ๅL้ฝ้่ฆX๏ผ, ไธคไธชpointer๏ผ้ๅฐXๅพๅ่ทณ |
| 826. Most Profit Assigning Work | O(mlogm + nlogn) | O(1) | Medium | ๐๐
|
| 828. Unique Letter String | O(n) | O(1) | Hard | ๐๐
|
| 838. Push Dominoes | O(n) | O(n) | Medium | ๐ ๐ ๐ |
| 844. Backspace String Compare | O(m+n) | O(1) | Easy | ไธคไธชpt๏ผ้ฝไปs,t ไปๅๅพๅๅฏนๆฏ |
| 986. Interval List Intersections | O(m+n) | O(1) | Medium |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 056. Merge Intervals | O(nlogn) | O(n) | Medium | ็ฑปไผผ็้ข |
| 057. Insert Interval | O(nlogn) | O(n) | Hard | ็ฑปไผผ็้ข |
| 075. Sort Colors | O(n) | O(1) | Medium | ๐ Tri Partition, ๅฐ็ๆพๅ้ข, ๅคง็ๆพๆๅ |
| 088. Merge Sorted Array | O(n) | O(1) | Easy | โไปๅๅพๅ |
| 147. Insertion Sort List | O(n^2) | O(1) | Medium | ่ท148. Sort List ไธๆ ท |
| 148. Sort List | O(nlogn) | O(logn) | Medium |
|
| 164. Maximum Gap | O(n) | O(n) | Hard | ๐๐
|
| 164. Maximum Gap | O(n) | O(n) | Hard | ๐๐
|
| 179. Largest Number | O(nlogn) | O(n) | Medium | โ๏ธโ๏ธ Python Lambda Sort |
| 218. The Skyline Problem | O(nlogn) | O(logn) | Hard | ๐๐ priority_queue or multiset(็critical point) |
| 274. H-Index | O(n) | O(n) | Medium | โcounting Sort |
| 315. Count of Smaller Numbers After Self | O(nlogn) | O(n) | Hard | MergeSort, BIT |
| 324. Wiggle Sort II | O(n) average | O(1) | Medium | โ(1 + 2*index) % (n | 1)ไฟ่ฏmedianๅทฆ้ขๆฐmapๅฅๆฐไฝ๏ผmediamๅณ้ข็ๆฐmapๅถๆฐไฝ
|
| 327. Count of Range Sum | O(nlogn) | O(n) | Hard | MergeSort with Count, BIT |
| 347. Top K Frequent Elements | O(n) | O(n) | Medium | ๐ Bucket Sort, Quick Select,
|
| 406. Queue Reconstruction by Height | O(n * sqrt(n))~O(n^2) | O(n) | Medium | ๐ ๅ ณ้ฎๆฏ่ฎคๆธ sort็้กบๅบ ๅ ๆheightๅคง็ๅฎๆไบ๏ผๅฆๆheightไธๆ ทๅsort kๆๅฐๅฐๅคงใ sqrt(n)่งฃๆฏไธๆ ท็sort๏ผไฝๆฏๆsortไนๅ็ๆๅ ฅๅฐไธๅ็็ปไธญ๏ผๆฏไธช็ปไธ่ถ ่ฟsqrt(n)ไธชๅ ็ด |
| 462. Minimum Moves to Equal Array Elements II | O(nlogn) | O(n) | Medium | MediumๆฏๆๅฐๅSum of Absolute Deviations; Quick Select: O(n) on average |
| 451. Sort Characters By Frequency | O(n) | O(n) | Medium | Bucket Sort, Quick Select(n-th elements) O(nlogn), priority_queue O(nlogn) |
| 692. Top K Frequent Words | O(nlogk) | O(n) | Medium | Bucket Sort, Quick Select(n-th elements), priority_queue |
| 853. Car Fleet | O(nlogn) | O(n) | Medium | Greedy: sort postionๅๅคงๅฐๅฐ๏ผๅsortๅฐtarget็ๆถ้ด็ฑๅฐๅฐๅคง |
| 1029. Two City Scheduling | O(n) average | O(n) | Easy | Greedyๆๆณ,quick select |
| C++priority_queue<pair<int,int>>pq ๅ
ๅฏนๆฏfirst, topๆฏfirstๆๅคง็๏ผ constructor: greater<int>ๆฏ่ฎฉtop่ฟๅๆๅฐ็ๆฐ,ๅคง็ๆฐๆพๅ้ข |
python็heappop()ๅ popๅฏนๆฏfirst,then second, topๆฏfirstๆๅฐ็ | |||
| 1365 How Many Numbers Are Smaller Than the Current Number | O(n+m) | O(m) | Easy | ๐O(n+m) Solution Counting Sort ๐Python Counting Sort |
| 1366. Rank Teams by Votes | O(n) | O(1) | Medium | ๐Python Sort list based on Dictonary value |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 095. Unique Binary Search Trees II | O(4^n / n^(3/2)) | O(4^n / n^(3/2)) | Medium | ๐ ๐loop start -> end. Generate vector of left subtree ๅright subtree, ็ถๅๆๅ็ปๅๆไปไปฌๅผๅจไธ่ตท |
| 096. Unique Binary Search Trees | O(n) | O(1) | Medium | DP, cartesian product ไฝไธบroot๏ผsum(#left + #right) Catalan number |
| 098. Validate Binary Search Tree | O(n) | O(1) | Medium | ็จprev ็น, iterative + recurssion |
| 100. Same Tree | O(n) | O(h) | Easy | โ |
| 104. Maximum Depth of Binary Tree | O(n) | O(h) | Easy | โ |
| 105. Construct Binary Tree from Preorder and Inorder Traversal | O(n) | O(h) | Medium | ๐๐ ๐๐ๆณจๆๅ889. Construct Binary Tree from Preorder and Postorder Traversal stack็ๅบๅซ. preorder ็ฌฌไธไธชๆฏtree็root, inorder ไธญroot->valๅทฆ้ขroot็left tree,ๅณ้ขroot็right tree, |
| 106. Construct Binary Tree from Inorder and Postorder Traversal | O(n) | O(h) | Medium | ๐๐ ๐๐ O(1) memory ๅ stack |
| 108. Convert Sorted Array to Binary Search Tree | O(n) | O(logn) | Easy | โ ่ท095. Unique Binary Search Trees II้ป่พไธๆ ท binary tree height ้่ฆbalanced |
| 109. Convert Sorted List to Binary Search Tree | O(n) | O(logn) | Medium | ๐ๆณจๆO(N)็่งฃ๏ผไธๆฏtwo pointer็ |
| 110. Balanced Binary Tree | O(n) | O(h) | Medium | ๐ ่ท095. Unique Binary Search Trees II็ฑปไผผ ็จbottom-up ๆฏtop-down ๆดefficient |
| 111. Minimum Depth of Binary Tree | O(n) | O(h) | Medium | โif not left: return h(r.right)+1; , if not right: return h(r.left)+1; else: return min(h(r.right), h(r.left))+1; |
| 114. Flatten Binary Tree to Linked List | O(n) | O(h) | Medium | ๐๐ preorder ็reverse |
| 116. Populating Next Right Pointers in Each Node | O(n) | O(1) | Medium | ๅฎก้ข: perfect binary tree
|
| 124. Binary Tree Maximum Path Sum | O(n) | O(h) | Hard | ๐not hard question |
| 129. Sum Root to Leaf Numbers | O(n) | O(h) | Medium | O(1) extra memory |
| 241. Different Ways to Add Parentheses | O(n* 4^n / n^(3/2)) | O(n * 4^n / n^(3/2)) | Medium | ๐ ็ฎsignๅ็๏ผ็ฎsignๅ็,็ถๅๅๅๅๅ็permutationๅ |
| 337. House Robber III | O(n) | O(h) | Medium | ๐
Greedy Algorithm. ่ฟๅvector, vector[0]ๅญ็ๆฏ็จไธไธไธชๆๅคง็่ทๅๅผ๏ผvector[1]ๅญ็ๆฏไธ็จไธไธไธช ๆๅคง็่ทๅๅผ |
| 395. Longest Substring with At Least K Repeating Characters | O(n) | O(n) | Medium | ๐๐
|
| 404. Sum of Left Leaves | O(n) | O(h) | Easy | โ |
| 437. Path Sum III | O(n) | O(h) | Easy | ๐ไธๅฎ็จunorderedmap , ไธ่ฝ็จunordered_set, ๆฏๅฆ -5,5,-6,6,4, ่ฆsum = 4, ๅฏไปฅไป-5ๅฐ4 ๆ่
-6 ๅฐ4 |
| 669. Trim a Binary Search Tree | O(n) | O(h) | Easy | ๐ |
| 671. Second Minimum Node In a Binary Tree | O(n) | O(h) | Easy | โ |
| 761. Special Binary String | O(n^2) | O(n) | Hard | โBad problem description Divide-conquer, ๆๆฏไธชspecial string ๅๅๆๅฐ็special string,็ถๅsort |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 004. Median of Two Sorted Arrays | O(log(min(m, n))) | O(1) | Hard | ๐๐ ๐ |
| 033. Search in Rotated Sorted Array | O(log(n)) | O(1) | Medium | ๐๐ Similar Question: |
| 034. Find First and Last Position of Element in Sorted Array | O(log(n)) | O(1) | Medium | lowerbound/upperbound/EqualRange, lowerbound ๅฏไปฅconvert to int |
| 35. Search Insert Position | O(log(n)) | O(1) | Easy | |
| 069. Sqrt(x) | O(log(n)) | O(1) | Easy | ๐ Bit Solution similar Question |
| 074. search a 2D Matrix | O(logm + logn) | O(1) | Medium | lower_bound, upper_bound lambda |
| 081. Search in Rotated Sorted Array II | O(logn) | O(1) | Medium | ๐๐ Similar Question: |
| 153. Find Minimum in Rotated Sorted Array | O(logn) | O(1) | Medium | Similar Question: |
| 154. Find Minimum in Rotated Sorted Array II | O(logn) ~ O(n) | O(1) | Hard | Similar Question: |
| 162. Find Peak Element | O(logn) | O(1) | Medium | โ |
| 222. Count Complete Tree Nodes | O((logn)^2) | O(1) | Medium | ๆณจๆๅฎก้ข complete tree |
| 275. H-Index II | O(logn) | O(1) | Medium | |
| 278. First Bad Version | O(logn) | O(1) | Easy | |
| 300. Longest Increasing Subsequence | O(nlogn) | O(n) | Medium | ๐๐ ๐ ๐ ย similar question |
| 354. Russian Doll Envelopes | O(nlogn) | O(n) | Hard | ๐๐ similar question |
| 363. Max Sum of Rectangle No Larger Than K | O(min(m, n)^2 * max(m, n) * logn(max(m, n))) | O(max(m, n)) | Hard | ๐๐ ๐ , ๅฉ็จSet |
| 367. Valid Perfect Square | O(logn) | O(1) | Easy | Similar Question |
| 374. Guess Number Higher or Lower | O(logn) | O(1) | Easy | |
| 378. Kth Smallest Element in a Sorted Matrix | O(n * log(MAX - MIN) | O(1) | Medium | l=m[0][0], r=m[-1][-1], binary search ๆฏๅฆ่ณๅฐๆkไธชๆฐๅฐไบ็ญไบmid |
| 410. Split Array Largest Sum | O(nlogn) | O(1) | Hard | ๐ |
| 436. Find Right Interval | O(nlogn) | O(n) | Medium | map lower bound |
| 475. Heaters | O((m + n) * logn) | O(1) | Easy |
|
| 540. Single Element in a Sorted Array | O(logn) | O(1) | Medium | |
| 658. Find K Closest Elements | O(logn+k) | O(1) | Medium | x-arr[left-1]<=arr[right]-x ไฟ่ฏleftไธๅฎๆฏ่ตท็น๏ผrightๆฏๆๅๆฐๅ้ขไธไฝ |
| 668. Kth Smallest Number in Multiplication Table | O(log(mn)*min(n,n)) | O(1) | Hard | binary search [1,m*n], isValidๅคๆญๆฏๅฆๆ่ณๅฐๆkไธชelementๅจไนๆณ่กจไธญ |
| 719. Find K-th Smallest Pair Distance | O(nlogn + nlogw) | O(1) | Hard | sort nums, l=0, r = nums[-1]-nums[0], binary searchๆฏๅฆๆkไธชๆฐๅคงไบ็ญไบmidๅจnumไธญ |
| 744. Find Smallest Letter Greater Than Target | O(logn) | O(1) | Easy | ๅคๆญๆๅไธไธชๅญๆฏๆฏไธๆฏๅคงไบtarget, ๅคงไบ็่ฏ็จupperbound๏ผๅฆๅ่ฟๅ็ฌฌไธไธชchar |
| 786. K-th Smallest Prime Fraction | O(nlogr) | O(1) | Hard |
|
| 793.Preimage Size of Factorial Zeroes Function | O((logk)^2) | O(1) | Hard | l = 0, r=5*k, binary search midๆฏๅฆๆkไธช้ถ็0๏ผๆ็่ฏr=mid, ๅฆๅl = mid+1, ๆๅๅๅคๆญlๆฏๅฆๆkไธช0, ๆ็่ฏ่ฟๅ5,ๆฒกๆ็่ฏ่ฟๅ0 |
| 1385. Find the Distance Value Between Two Arrays | O((n + m) * logm) | O(1) | Easy | ๐ Binary Search, Two pointer |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 220. Contains Duplicate III | O(nlogn) | O(n) | Medium | set/multiset lower_bound ย ๆ่ python OrderedDict, ๆฏๆฌกpopitem(false) pop ๆๅ insert็ |
| 230 Kth Smallest Element in a BST | O(max(h, k)) | O(min(h, k)) | Medium | inorder traversals(ไปๆๅฐ็travelๅฐๆๅคง็) / stack |
| 235. Lowest Common Ancestor of a Binary Search Tree | O(h) | O(1) | Easy | ๅฉ็จย binary search tree็ๆง่ดจ |
| 352. Data Stream as Disjoint Intervals | O(logn) | O(n) | Hard | |
| 449. Serialize and Deserialize BST | O(n) | O(h) | Medium | preorder traversals |
| 450. Delete Node in a BST | O(h) | O(h) | Medium |
|
| 530. Minimum Absolute Difference in BST | O(n) | O(h) | Easy | ๅฉ็จbinary search tree็ๆง่ดจ ๆ่ inorder traversal ๅธฆ็ๅ้ขprev็node val |
| 783. Minimum Distance Between BST Nodes | O(n) | O(h) | Easy | ๅฉ็จbinary search tree็ๆง่ดจ ๆ่ inorder traversal ๅธฆ็ๅ้ขprev็node val(ไธ530้ข ่งฃๆณไธๆ ท) |
| 1382 Balance a Binary Search Tree | O(n) | O(h) | Medium |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 094. Binary Tree Inorder Traversal | O(n) | O(1) | Medium | Tree |
| 095. Unique Binary Search Trees II | O(4^n / n^(3/2)) | O(4^n / n^(3/2)) | Medium | ๐ ๐loop start -> end. Generate vector of left subtree ๅright subtree, ็ถๅๆๅ็ปๅๆไปไปฌๅผๅจไธ่ตท |
| 098. Validate Binary Search Tree | O(n) | O(1) | Medium | ็จprev ็น, iterative + recurssion |
| 099 Recover Binary Search Tree | O(n) | O(1) | Hard | Tree |
| 100. Same Tree | O(n) | O(h) | Easy | โ |
| 104. Maximum Depth of Binary Tree | O(n) | O(h) | Easy | โ |
| 101. Symmetric Tree | O(n) | O(h) | Easy | โ ๆณจ: iterative stack push ้กบๅบ |
| 108. Convert Sorted Array to Binary Search Tree | O(n) | O(logn) | Easy | โ ่ท095. Unique Binary Search Trees II้ป่พไธๆ ท binary tree height ้่ฆbalanced |
| 109. Convert Sorted List to Binary Search Tree | O(n) | O(logn) | Medium | ๐ๆณจๆO(N)็่งฃ๏ผไธๆฏtwo pointer็ |
| 110. Balanced Binary Tree | O(n) | O(h) | Medium | ๐ ่ท095. Unique Binary Search Trees II็ฑปไผผ ็จbottom-up ๆฏtop-down ๆดefficient |
| 111. Minimum Depth of Binary Tree | O(n) | O(h) | Medium | โif not left: return h(r.right)+1; , if not right: return h(r.left)+1; else: return min(h(r.right), h(r.left))+1; |
| 112. Path Sum | O(n) | O(h) | Easy | ๐(iterative Solution: ๅฆๆๆrightไผ็ป่ฟroot ไธคๆฌก)[https://github.com/beckswu/Leetcode/blob/master/DFS/112.%20Path%20Sum.cpp#L74] |
| 124. Binary Tree Maximum Path Sum | O(n) | O(h) | Hard | ๐not hard question |
| 129. Sum Root to Leaf Numbers | O(n) | O(h) | Medium | O(1) extra memory |
| 144. Binary Tree Preorder Traversal | O(n) | O(1) | Medium | Tree |
| 145. Binary Tree Postorder Traversal | O(n) | O(1) | Hard | Tree |
| 199 Binary Tree Right Side View | O(n) | O(h) | Medium | โ Easy |
| 222. Count Complete Tree Nodes | O((logn)^2) | O(1) | Medium | |
| 257 Binary Tree Paths | O(n * h) | O(h) | Easy | โ Easy |
| 404. Sum of Left Leaves | O(n) | O(h) | Easy | โ |
| 437. Path Sum III | O(n) | O(h) | Easy | unorderedmap ๅญ็ๅจ็ฐๅจ็นไนๅ็ <prefix sum, frequency> pairs. ไปไธญ้ดๆ็นๅฐ็ฐๅจsum = ไปrootๅฐ็ฐๅจ็นsum - rootๅฐไธญ้ดๆ็น็sum |
| 515. Find Largest Value in Each Tree Row | O(n) | O(h) | Medium | โ DFS / BFS |
| 538. Convert BST to Greater Tree | O(n) | O(h) | Easy | Tree |
| 543. Diameter of Binary Tree | O(n) | O(h) | Easy | Tree |
| 572. Subtree of Another Tree | O(m * n) | O(h) | Easy | |
| 617. Merge Two Binary Trees | O(n) | O(h) | Easy | |
| 623. Add One Row to Tree | O(n) | O(h) | Medium | |
| 637. Average of Levels in Binary Tree | O(n) | O(h) | Easy | |
| 653. Two Sum IV - Input is a BST | O(n) | O(h) | Easy | |
| 671. Second Minimum Node In a Binary Tree | O(n) | O(h) | Easy | โ |
| 687. Longest Univalue Path | O(n) | O(h) | Easy | |
| 669. Trim a Binary Search Tree | O(n) | O(h) | Easy | ๐ |
| 814. Binary Tree Pruning | O(n) | O(h) | Medium | |
| 863. All Nodes Distance K in Binary Tree | O(n) | O(h) | Medium | ๐๐Really good question! ไธๅฟ ็บ ็ปไบone pass, ้่ฆchild -> parent map |
| 865. Smallest Subtree with all the Deepest Nodes | O(n) | O(h) | Medium | ๐DFS, left level == right level ่ฟๅroot, if left level > right level, ่ฟๅleft dfs็node else่ฟๅright dfs็ |
| 889. Construct Binary Tree from Preorder and Postorder Traversal | O(n) | O(h) | Medium | ๐๐
|
| 1008. Construct Binary Search Tree from Preorder Traversal | O(n) | O(h) | Medium | ๐Stack / Morris Traversal |
| 1028. Recover a Tree From Preorder Traversal | O(n) | O(h) | Hard | ๐ stack / DFS, stack้ป่พ็ฑปไผผ889. Construct Binary Tree from Preorder and Postorder Traversal |
| 1367 Linked List in Binary Tree | O(n+l) | O(h+l) | Medium | |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 112. Path Sum | O(n) | O(h) | Easy | ๐iterative Solution: ๅฆๆๆrightไผ็ป่ฟroot ไธคๆฌก |
| 113 Path Sum II | O(n) | O(h) | Medium | ๐iterative Solution: ๅฆๆๆrightไผ็ป่ฟroot ไธคๆฌก |
| 199 Binary Tree Right Side View | O(n) | O(h) | Medium | โ Easy |
| 200 Number of Islands | O(m * n) | O(m * n) | Medium | โ๏ธ Union Find with Rank Heuristics, โ๏ธPython Complex number ่กจ็คบๅไธชDFS ๆนๅ |
| 236 Lowest Common Ancestor of a Binary Tree | O(n) | O(h) | Medium | ๐ Iterative Solution |
| 257 Binary Tree Paths | O(n * h) | O(h) | Easy | โ Easy |
| 282 Expression Add Operators | O(4^n) | O(n) | Hard | ๐
้พ็น: ๅผๆธ
cv (cumulative sum), pv(previous sum) ๅ
ณ็ณป, pos ๅฐ็ฐๅจprocess็index๏ผๆณจๆ:
|
| 301. Remove Invalid Parentheses | O(C(n, c)) | O(c) | Hard | ๐๐Complexity Analysis
|
| 329. Longest Increasing Path in a Matrix | O(m * n) | O(m * n) | Hard | ๐ |
| 332. Reconstruct Itinerary | O(t! / (n1! * n2! * ... nk!)) | O(t) | Medium | ๐
|
| 399. Evaluate Division | O(q*|V|!) | O(e) | Medium | DFS with memiozation ็จunordered_map, vector, unordered_set่ฎฐๅฝๆฏๅฆ็ป่ฟ๏ผ ่ท329. Longest Increasing Path in a Matrix็ฑปไผผ |
| 417. Pacific Atlantic Water Flow | O(m * n) | O(m * n) | Medium | ๐๐ bit mask, ้พ็น: ่ตท็นๅฟ ้กปๆฏๅไธช่พน |
| 440. K-th Smallest in Lexicographical Order | O(logn) | O(logn) | Hard | ๆพ่งๅพ, ไธ่ฝไธไธชไธไธช็ฎ, ่ฆ่ทณ็ผฉๅๅบ้ด |
| 464. Can I Win | O(n!) | O(n) | Medium | ๐DFS+Memoization ้พ็น: Memoization่ฎฐๅฝ็ไธ่ฝๆฏ่ฟๅฉๅคๅฐๅฐtarget, ่ฎฐๅฝๆฏ็ฐๅจๅฏ้ๆฉ็set่ฝไธ่ฝ่ตข |
| 515. Find Largest Value in Each Tree Row | O(n) | O(h) | Medium | โ DFS / BFS |
| 547. Friend Circles | O(n^2) | O(n) | Medium | Union Find with Rank Heuristic / DFS |
| 638. Shopping Offers | O(n * 2^n) | O(n) | Medium | ๐ โ๏ธ [่ฎพ่ฎกไธไธชๅฅฝ็DFS structure](https://github.com/beckswu/Leetcode/blob/master/DFS/638.%20Shopping%20Offers.cpp#L42] |
| 690. Employee Importance | O(n) | O(h) | Easy | ้่ฆ็จunordered_map, ๅ ไธบvector index ไธ็ญๅไบ id |
| 695. Max Area of Island | O(m*n) | O(m*n) | Medium | โ๏ธPython Complex number ่กจ็คบๅไธชDFS ๆนๅ |
| 733. Flood Fill | O(m*n) | O(m*n) | Easy | โ |
| 749. Contain Virus | O((m * n)^(4/3)) | O(m * n) | Hard | ๐ DFS/BFS, every step try each possibility see where is max new Infection area, then build wall and update grid |
| 753. Cracking the Safe | O(k^n) | O(k^n) | Hard | ๐ Greedy + BrainStorming, ้พ็น:ๅฆๆ่ฎพ็ฝฎ่ตทๅงๆฐๅญ๏ผๅฆไฝLoop ไธไผๆdeadlock |
| 756. Pyramid Transition Matrix | O(a^b) | O(a^b) | Medium | bottom-up, bit mask |
| 785. Is Graph Bipartite? | O(|V+E|) | O(|V|) | Medium | DFS/BFS + Bit Mask, ็จ็บข่ไธค่ฒ่กจvertex๏ผๅฆๆ็ธ้ป็node ไธๆ ท้ข่ฒ return false |
| 797. All Paths From Source to Target | O(p + r * n) | O(n) | Medium | โ |
| 802. Find Eventual Safe States | O(|V+E|) | O(|V|) | Medium | ๐ DFS + bit mask ้่ฆๅฎไนstate 0๏ผunvisited, 1 visited not safe, 2 visited not safe, 3 visited and safe ๆณจๆไธ่ฝ็จvisited ็value ไปฃๆฟboolean ็value |
| 886. Possible Bipartition | O(|V+E|) | O(|V+E|) | Medium | DFS, BFS |
| 980. Unique Paths III | O((m * n) * 2^(m * n)) | O((m * n) * 2^(m * n)) | Medium | DFS, BFS |
| 1367 Linked List in Binary Tree | O(n+l) | O(h+l) | Medium | KMP ๐C++ ็จconst auto [] get function return pair |
| 1368 Minimum Cost to Make at Least One Valid Path in a Grid | O(m*n) | O(m*n) | Medium | BFS + DFS |
| 1377. Frog Position After T Seconds | O(n) | O(n) | Hard | โ๏ธPython Set |
| 1391. Check if There is a Valid Path in a Grid | O(m*n) | O(1) | Medium | |
| 1397. Count Number of Teams | O(m*n) | O(m) | Hard | DFS /DP + KMP ๐ ๐ ย |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 017. Letter Combinations of a Phone Number | O(n * 4^n) | O(n) | Medium | โ๏ธPython Lambda Function |
| 022. Generate Parentheses | O(4^n / n^(3/2)) | O(n) | Medium | โ๏ธPython Trick |
| 037. Sudoku Solver | O((9!)^9) | O(1) | Hard | ๅฏไปฅ็จbit mask |
| 039. Combination Sum | O(k * n^k) | O(k) | Medium | โ๏ธPython Trick, Difference between yield and return |
| 040. Combination Sum II | O(n * n!) | O(n) | Medium |
|
| 216. Combination Sum III | O(k * C(n, k)) | O(k) | Medium | ๐Python itertools.combination |
| 046. Permutations | O(\n * n!) | O(n) | Medium |
|
| 047. Permutations II | O(\n * n!) | O(n) | Medium | |
| 051. N-Queens | O(n!) | O(n) | Hard | ๐Python Solution |
| 052. N-Queens-II | O(n!) | O(n) | Hard | โ ไธ051. N-Queens ้ป่พไธๆ ท |
| 077. Combinations | O(k * C(n, k)) | O(k) | Medium | ๐ Python Multiple Solution |
| 079. Word Search | O(m * n * l) | O(l) | Medium | Simple DFS. smart way: ๆvisited็ๅญๆฏๆนไบ ็ๆไบhashset, visited |
| 093. Restore IP Addresses | O(1) | O(1) | Medium | recursive & iterative |
| 078. Subsets | O(n * 2^n) | O(1) | Medium | ๐๐ |
| 090. Subsets II | O(n * 2^n) | O(1) | Medium | recursive(้ป่พ็ฑปไผผ040. Combination Sum II) & ๐๐ iterative๏ผๆๆฐ๏ผ |
| 126. Word Ladder II | O(n * d) | O(d) | Hard |
|
| 131. Palindrome Partitioning | O(n^2) ~ O(2^n) | O(n^2) | Medium | ๐Python Solution |
| 140. Word Break II | O(n * l^2 + n * r) | O(n^2) | Hard | ๐ DFS with Memoization, ๆฒกๆmemoization TLE, โ๏ธC++ Std:function |
| 212. Word Search II | O(m * n * l) | O(l) | Hard | Suffix Trie (backtracking ๆฏๆboard ๆๆถๆนไบ, ็ๅปไบhashset visited), ้พๅบฆmediumๅทฆๅณ, โ๏ธPython Complex number ่กจ็คบๅไธชDFS ๆนๅ, Dictionary setdefault |
| 526. Beautiful Arrangement | O(n!) | O(n) | Medium | swap, ๆณจๆif ๆกไปถ, ๐Python Solution |
| 676. Implement Magic Dictionary | O(n) | O(d) | Medium |
|
| 679. 24 Game | O(1) | O(1) | Hard | Complexity: upper bound of 12* 6 * 2 * 4 * 4 * 4 = 9216 possibilities๐๐ Python Solution |
| 698. Partition to K Equal Sum Subsets | O(n* 2^n) | O(2^n) | Medium | ๐๐ ้ๅธธ็ปๅ
ธ้ข็ฎ,
|
| 718. Maximum Length of Repeated Subarray | O(m * n) | O(min(m, n)) | Medium | ๐ DP |
| 784. Letter Case Permutation | _O(n * 2^n) _ | O(1) | Easy | โ๏ธPython itertools.product |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 1361. Validate Binary Tree Nodes | O(n) | O(n) | Medium | DFS |
DFS ๆฏ็ๆๆฒกๆpath๏ผDPๆฏ็ๆๅ ไธชpath
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 010. Regular Expression Matching | O(m*n) | O(n) | Hard | ๐ ๐ |
| 044. Wildcard Matching | O(n*m) | O(1) | Hard | dp or greedy (Greedyไนๆฏ O(n*m) ) |
| 053. Maximum Subarray | O(n) | O(1) | Easy | ๐ ๆดๆฐres, minsum ็้กบๅบ |
| 062. Unique Paths | O(m * n) | O(m + n) | Medium | |
| 063. Unique Paths II | O(m * n) | O(m + n) | Medium | |
| 064. Minimum Path Sum | O(m * n) | O(m + n) | Medium | |
| 070. Climbing Stairs | O(n) | O(1) | Easy | |
| 072. Edit Distance | O(m*n) | O(m+n) | Hard | ็ฑปไผผ็้ข: |
| 087. Scramble String | O(n^4) | O(n^3) | Hard | ๐ Memoization |
| 091. Decode Ways | O(n) | O(1) | Medium | ๐๐๐ similar question: 062. Unique Paths, 070. Climbing Stairs 509. Fibonacci Number |
| 097. Interleaving String | O(m*n) | O(m+n) | Hard | ๐ DP, DFS, BFS |
| 115. Distinct Subsequences | O(n^2) | O(n) | Hard | ๐
๐
็ฑปไผผ็้ข: |
| 120. Triangle | O(m*n) | O(n) | Medium | Bottom-up DP |
| 123. Best Time to Buy and Sell Stock III | O(n) | O(n) | Hard | ๐
๐
Why variables order doesn't matter ็ฑปไผผ |
| 132. Palindrome Partitioning II | O(n^2) | O(n) ~O(n) |
Hard | ๐
๐
็ฑปไผผ็้ข: |
| 139. Word Break | O(n^2) | O(n) | Medium |
|
| 152. Maximum Product Subarray | O(n) | O(1) | Medium | ๐ ๐ Prefix Product, Suffix Product |
| 174. Dungeon Game | O(n+m) | O(n)~O(1) | Hard | ๐ bottom-up DP, Can't start at (0,0) |
| 188. Best Time to Buy and Sell Stock IV | O(k*n) | O(n) | Hard | ็ฑปไผผ็้ข |
| 198. House Robber | O(n) | O(1) | Easy | Top-down / bottom-up ็ฑปไผผ็้ข: |
| 213. House Robber II | O(n) | O(1) | Medium | ๅๆไธคไธชhouse rob้ฎ้ข๏ผ
็ฑปไผผ็้ข: |
| 221. Maximal Square | O(n^2) | O(n) | Medium | ็ฑปไผผ็้ข: |
| 279. Perfect Squares | O(n * sqrt(n) | O(n) | Medium | Bottom-Up DP, Top-Down DP,BFS. Similar Question |
| 304. Range Sum Query 2D - Immutable | ctor: O(m * n), lookup: O(1) | O(m+n) | Medium | ็ฑปไผผ็้ข: |
| 309. Best Time to Buy and Sell Stock with Cooldown | O(n) | O(1) | Medium | |
| 312. Burst Balloons | O(n^3) | O(n^2) | Hard | Top-Down / Bottom-up, Similar Question: 546. Remove Boxes |
| 322. Coin Change | O(n*k) | O(k) | Medium | Bottom-up, Top-Down, BFS, Similar Question |
| 338. Counting Bits | O(n) | O(n) | Medium | Math ๆพ่งๅพ |
| 357. Count Numbers with Unique Digits | O(n) | O(1) | Medium | ๐ DP, Static DP, backtracking |
| 368. Largest Divisible Subset | O(n^2) | O(n) | Medium | ๐
๐
Key: a < b < c, if c % b = 0 and b % a = 0 Then c % a == 0 ็ฑปไผผ้ข๏ผ |
| 375. Guess Number Higher or Lower II | O(n^2) | O(n^2) | Medium | ๐ |
| 377. Combination Sum IV | O(nlogn + n * t) | O(t) | Medium | Similar Question |
| 403. Frog Jump | O(n^2) | O(n^2) | Hard | ็ปๅ ธ, TopDown, Bottom-up, BFS |
| 416. Partition Equal Subset Sum | O(n*s) | O(s) | Medium | backtracking / DP |
| 446. Arithmetic Slices II - Subsequence | O(n^2) | O(n*d) | Hard | ๐ |
| 466. Count The Repetitions | O(s1 * min(s2, n1)) | O(s2) | Hard | ๐ ๐ |
| 467. Unique Substrings in Wraparound String | O(n) | O(1) | Medium | ็ปๅ ธ๐ ๐ |
| 472. Concatenated Words | O(n * l^2) | O(l) | hard | suffix Trie |
| 474. Ones and Zeroes | O(s *m * n) | O(s *m * n) | Medium | ็ปๅ ธ๐ , Top-Down, Bottom-up |
| 486. Predict the Winner | O(n^2) | O(n) | Medium | ็ปๅ ธ๐ ๐ , DP่งฃ, DFS |
| 514. Freedom Trail | O(k) ~ O(k * r^2) | O(r) | Hard | ็ปๅ ธ๐ ๐ , Top-Down, Bottom-upย |
| 516. Longest Palindromic Subsequence | O(n^2) | O(n) | Medium | ็ปๅ
ธ๐
, Bottom-up, Top-Down ็ฑปไผผ็้ข: |
| 518. Coin Change 2 | O(n^2) | O(n) | Medium | ็ปๅ ธ๐ TopDown, Bottom-up |
| 546. Remove Boxes | O(n^3) ~ O(n^4) | O(n^3) | Hard | ๐ ๐ ๐ Top-Down, Bottom-up, Similar Question: 312. Burst Balloons |
| 552. Student Attendance Record II | O(n) | O(1)~O(n) | Hard | ๐ Derive Relation |
| 576. Out of Boundary Paths | O(N * m * n) | O(m * n) | Medium | DP, DFS, BFS |
| 583. Delete Operation for Two Strings | O(m*n) | O(n) | Medium | Edit Distance without replace ็ฑปไผผ้ข: |
| 600. Non-negative Integers without Consecutive Ones | O(1) | O(1) | Hard | ๐ ๐ Math & Bit |
| 629. K Inverse Pairs Array | O(n*k) | O(k) | Hard | ๐ ๆพ่งๅพ |
| 639. Decode Ways II | O(n) | O(1) | Hard | ๐
ๅทง่งฃ ็ฑปไผผ็้ข: 091. Decode Ways |
| 650. 2 Keys Keyboard | O(sqrt(n)) | O(1) | Medium | ๐ Greedy / DP prime factoring |
| 664. Strange Printer | O(n^3) | O(n^2) | Hard | ๐
๐
็ฑปไผผ็้ข: |
| 673. Number of Longest Increasing Subsequence | O(n^2) | O(n) | Medium | ๐๐ ๐ |
| 688. Knight Probability in Chessboard | O(k*n^2) | O(k*n^2) ~O(n^2) |
Medium | ๐ Bottom-up, Top-Down |
| 689. Maximum Sum of 3 Non-Overlapping Subarrays | O(n) | O(n) | Hard | ๐
๐
๐
sliding windows/ DP similar to Stock Purchasing ็ฑปไผผ็้ข |
| 691. Stickers to Spell Word | O(2^T*S*T) | O(2^T) | Hard | ๐ ๐ ๐ |
| 712. Minimum ASCII Delete Sum for Two Strings | O(m*n) | O(m*n) ~O(n) |
Medium | Edit Distance ็ฑปไผผ็้ข: |
| 714. Best Time to Buy and Sell Stock with Transaction Fee | O(n) | O(n) | Medium | |
| 730. Count Different Palindromic Subsequences | O(n^2) | O(n) | Hard | HardไธญHard ๐ ๐ ๐ |
| 740. Delete and Earn | O(n) | O(n) | Medium | ็ฑปไผผ็้ข: |
| 741. Cherry Pickup | O(n^3) | O(n^2) | Hard | ๐ ๐ ๐ |
| 746. Min Cost Climbing Stairs | O(n) | O(1) | Easy | |
| 764. Largest Plus Sign | O(n^2) | O(n^2) | Medium | Maximal Square, ไปๅทฆๅฐๅณ๏ผไปไธๅฐไธ๏ผไปๅณๅฐๅทฆ๏ผไปไธๅฐไธ,ๆดๆฐๆๅฐ็count ็ฑปไผผ็้ข: |
| 788. Rotated Digits | O(n)~O(logn) | O(n)~O(logn) | Easy | ๐ ๐ ๐ |
| 790. Domino and Tromino Tiling | O(n) | O(n)~O(1) | Medium | ๐ ๐ Math ๆพ่งๅพ |
| 799. Champagne Tower | O(n^2) | O(n^2)~O(n) | Medium | |
| 801. Minimum Swaps To Make Sequences Increasing | O(n) | O(1) | Medium | ๐ |
| 805. Split Array With Same Average | O(n^4) | O(n^3) | Hard | ๐ ๐ ๐ ๐ totalSum/n = Asum/k = Bsum/(n-k) |
| 808. Soup Servings | O(1) | O(1) | Medium | |
| 813. Largest Sum of Averages | O(k*n^2) | O(n) | Medium | ๐๐ ๐ ๐ |
| 818. Race Car | O(nlogn) | O(n) | Hard | ๐ ๐ ๐ |
| 823. Binary Trees With Factors | O(n^2) | O(n) | Medium | ็ฑปไผผ้ข๏ผ ย |
| 837. New 21 Game | O(n) | O(n) | Medium | ๐ ๐ ๐ |
| 847. Shortest Path Visiting All Nodes | O(n*2^n) | O(n*2^n) | Hard | BFS/DP๐ |
| 877. Stone Game | O(n^2) | O(n) | Medium | Strategy |
| 879. Profitable Schemes | O(n*g*p) | O(g*p) | Hard | ๐๐ |
| 903. Valid Permutations for DI Sequence | O(n^2) | O(n) | Hard | ๐๐ ๐ |
| 920. Number of Music Playlists | O(n*l) | O(n) | Hard | ๐ ๐ ๐ |
| 926. Flip String to Monotone Increasing | O(n) | O(n) | Medium | ๐๐ ๐ |
| 931. Minimum Falling Path Sum | O(n^2) | O(n) | Medium | |
| 926. Flip String to Monotone Increasing | O(n) | O(n) | Medium | ๐ |
| 935. Knight Dialer | O(logn) | O(1) | Medium | ๐Citadel็้ข. Matrix Exponentiationย |
| 940. Distinct Subsequences II | O(n) | O(1) | Medium | ๐๐ ย |
| 943. Find the Shortest Superstring | O(n^2 * 2^n) | O(n^2) | Medium | ๐ ๐ ๐ Travelling Salesman Problemย |
| 956. Tallest Billboard | O(n * 3^(n/2)) | O(3^(n/2)) | Hard | ๐ ๐ ๐ Knapsnackย |
| 960. Delete Columns to Make Sorted III | O(n * l^2) | O(l) | Hard | ๐ ็ฑปไผผ็้ข: ย |
| 975. Odd Even Jump | O(nlogn) | O(n) | Hard | ๐๐ ๐ ๐ , Mono Stack/BST |
| 983. Minimum Cost For Tickets | O(n) | O(1) | Medium | ๐๐ ๐ Similar Question |
| 1277. Count Square Submatrices with All Ones | O(m*n) | O(1) | Medium | ย ็ฑปไผผ็้ข: |
| 1387. Sort Integers by The Power Value | O(n) average | O(n) | Medium | nth_element, โ๏ธโ๏ธC++ Static Variable Python Static Variableย |
| 1388. Pizza With 3n Slices | O(n^2) | O(n) | Hard | ๐๐ ็ฑปไผผ213. House Robber II ๅย 188. Best Time to Buy and Sell Stock IV |
| 1395. Count Number of Teams | O(n^2) | O(1) | Medium | ย |
| 1411. Number of Ways to Paint N ร 3 Grid | O(logn) | O(1) | Medium | ๐๐ Matrix Exponentiationย |
| 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons | O(n*m*k) | O(m*k) | Hard | ๐ ย |
| ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 146. LRU Cache | O(1) | O(k) | Medium |
|
| 380. Insert Delete GetRandom O(1) | O(1) | O(1) | Medium | ๐ ๐ |
| 1381. Design a Stack With Increment Operation | ctor: O(1) |
|||
| push: O(1) |
||||
| pop: O(1) |
||||
| increment: O(1) | O(n) | Medium | Lazy increment | |
| [1396. Design Underground System](1396 Design Underground System) | ctor: O(1) |
|||
| checkin: O(1) |
||||
| checkout: O(1) |
||||
| getaverage: O(1) | O(n) | Medium |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 192 Word Frequency | O(n) | O(k) | Medium | switch column awk, remove whitespace sed |
| 193. Valid Phone Numbers | O(n) | O(1) | Easy | grep |
| 194 Transpose File Shell | O(n^2) | O(n^2) | Medium | paste & cut |
| 195. Tenth Line | O(n) | O(1) | Easy | awk, sed |