[0003] - M - Longest Substring Without Repeating Characters -
[Python]
[CPP] -
[Video] -
[Two Pointers][Sliding Window]
[0004] - H - Median of Two Sorted Arrays -
[Python]
[CPP] -
[Video] -
[Binary Search]
- Binary search on two sorted array
- Find Kth element on two sorted array
- Find Kth element on N sorted array?
[0005] - M - Longest Palindromic Substring -
[Python]
[CPP] -
[Video] -
[Palindrome][Manacher]
- [1960]
- Manacher （马拉车） - O(N)
- KMP (string manipulation)
[0013] - E - Roman to Integer -
[Python]
[CPP] -
[Video] -
[Recursion]
[0014] - E - Longest Common Prefix -
[Python]
[CPP] -
[Video] -
[Analysis]
[0015] - M - 3Sum -
[Python]
[CPP] -
[Video] -
[Two Pointers][classic]
[0019] - M - Remove Nth Node From End of List -
[Python]
[CPP] -
[Video] -
[LinkedList][Two Pointers]
[0020] - E - Valid Parentheses -
[Python]
[CPP] -
[Video] -
[Stack]
[0022] - M - Generate Parentheses -
[Python]
[CPP] -
[Video] -
[Recursive]
[0032] - H - Longest Valid Parentheses -
[Python]
[CPP] -
[Video] -
[parentheses]
- when you see pairing -> stack
[0033] - M - Search in Rotated Sorted Array -
[Python]
[CPP] -
[Video] -
[Binary Search]
- [0081]
[0042] - H - Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/description/) -
[Python]
[CPP] -
[Video] -
[Monotonic Stack][Tow pointers]
- Method I: two pass
- Method II: monotonic stack
- Method III: two pointers
- How to get left-max/right-max
- One pass monotonic stack
- [0084]
- [2334]
[0045] - M - Jump Game II -
[Python]
[CPP] -
[Video] -
[Greedy]
[0046] - M - Permutations -
[Python]
[CPP] -
[Video] -
[Permutation]
[0047] - M - Permutations II -
[Python]
[CPP] -
[Video] -
[Permutation]
[0049] - M - Group Anagrams -
[Python]
[CPP] -
[Video] -
[Patterns]
[0053] - M - Maximum Subarray -
[Python]
[CPP] -
[Video] -
[DP][Kadane][classic]
-
Kadane variation: 2272:
- max subarray sum that requires two elements
* regular kadane dp[i]=max(nums[i], dp[i-1]+nums[i]) * Kadane Variation dp0[i]: the max subarray sum ending @ i and this subarray does NOT contain -1 dp1[i]: the max subarray sum ending @ i and this subarray DOES contains -1 for(int ii=0; ii<N; ++ii){ if(nums[ii]==1){ dp0[ii]=max(1, 1+dp0[ii-1]); dp1[ii]=dp1[ii-1]+1; }else{ dp0[ii]=0 dp1[ii]=-1+max(dp0[ii-1], dp1[ii-1]) } ret=max(ret, dp1[ii ]) }
[0055] - M - Jump Game -
[Python]
[CPP] -
[Video] -
[DP][Jump Game]
[0056] - M - Merge Intervals -
[Python]
[CPP] -
[Video] -
[Interval]
[0072] - M - Edit Distance -
[Python]
[CPP] -
[Video] -
[DP]
[0075] - M - Sort Colors -
[Python]
[CPP] -
[Video] -
[Two Pointers]
[0078] - M - Subsets -
[Python]
[CPP] -
[Video] -
[Subsets]
[0079] - M - Word Search -
[Python]
[CPP] -
[Video] -
[DFS]
-
backtrack -> no memo
[0081] - M - desc - [Python] [CPP] - [Video] - [
Binary Search] -
[0033]
-
search rotated array
[0084] - H - Largest Rectangle in Histogram -
[Python]
[CPP] -
[Video] -
[Monotonic Stack][Count Subarray by Element]
- Monotonic stack one pass
- The best way to find prev_smaller (NOT prev_smaller_equal)
[0088] - E - Merge Sorted Array -
[Python]
[CPP] -
[Video] -
[K-way merge]
[0090] - M - Subsets II -
[Python]
[CPP] -
[Video] -
[Subsets]
[0121] - E - Best Time to Buy and Sell Stock -
[Python]
[CPP] -
[Video] -
[Best Time Buy/Sell Stock]
[0123] - H - Best Time to Buy and Sell Stock III
-
[Python]
[CPP] -
[Video] -
[DP]
[0126] - H - desc -
[Python]
[CPP] -
[Video] -
[BFS][DFS]
- beware of the local_visited concept, we cannot add visited until all nodes same level are processed complete
[0127] - H - Word Ladder -
[Python]
[CPP] -
[Video] -
[Patterns]
[0134] - M - Gas Station -
[Python]
[CPP] -
[Video] -
[Greedy]
[0135] - H - Candy -
[Python]
[CPP] -
[Video] -
[Greedy]
- [1840]
- [1846]
[0139] - M - Word Break - [Python] [CPP] - [Video]
[0140] - H - Word Break II -
[Python]
[CPP] -
[Video] -
[Trie]
[0146] - M - LRU Cache -
[Python]
[CPP] -
[Video] -
[Design][OrderedDict]
# OrderedDict
# front is the most recent used
# last is the least recent used
cache = OrderedDict()
* od.move_to_end()
* cache.popitem(last=False) # pop the last- [0432]
- [0472] Concatenated Words
[0153] - M - Find Minimum in Rotated Sorted Array -
[Python]
[CPP] -
[Video] -
[Binary Search]
[0154] - H - Find Minimum in Rotated Sorted Array II -
[Python]
[CPP] -
[Video] -
[Binary Search]
[0155] - E - Min Stack -
[Python]
[CPP] -
[Video] -
[Stack]
[0188] - H - Best Time to Buy and Sell Stock IV -
[Python]
[CPP] -
[Video] -
[DP][Binary Search]
- [0122]: buy sell unlimited
- [0714]: buy sell with fee
- Alian Trick
[0198] - E - House Robber -
[Python]
[CPP] -
[Video] -
[DP][Classic][DP - Type I Basic]
[0200] - M - Number of Islands -
[Python]
[CPP] -
[Video] -
[DFS][classic]
[0206] - E - Reverse Linked List -
[Python]
[CPP] -
[Video] -
[LinkedList]
[0207] - M - Course Schedule -
[Python-BFS]
[Python-DFS]
[CPP] -
[Video] -
[Topology Sort][Classics]
[0210] - - Course Schedule II -
[Python]
[CPP] -
[Video] -
[Topology Sort]
[0212] - H - Word Search II -
[Python]
[CPP] -
[Video] -
[Trie]
[0213] - M - House Robber II -
[Python]
[CPP] -
[Video] -
[DP]
[0215] - M - Kth Largest Element in an Array -
[Python]
[CPP] -
[Video] -
[Quick Select]
[0224] - H - Basic Calculator -
[Python]
[CPP] -
[Video] -
[Expression Parsing][Basic Calculator]
[0232] - E - Implement Queue using Stacks -
[Python]
[CPP] -
[Video] -
[Stack]
[0239] - H - Sliding Window Maximum -
[Python]
[CPP] -
[Video] -
[deque][sorted list][bisect][SortedList]
- [862]
- [1425]
- [1438]
- O(1) time output max value in sliding window
- find max in sliding window
[0240] - M - Search a 2D Matrix II -
[Python]
[CPP] -
[Video] -
[Matrix]
[0242] - E - Valid Anagram -
[Python]
[CPP] -
[Video] -
[Anagram]
[0252] - E - Meeting Rooms -
[Python]
[CPP] -
[Video] -
[Intervals][Sweep Line]
[0253] - M - Meeting Rooms II -
[Python]
[CPP] -
[Video] -
[Intervals]
[0256] - M - Paint House -
[Python]
[CPP] -
[Video] -
[DP]
- N houses, cost of black is a, cost of white is b. cannot paint 3 houses with same color consequtively. what's the min cost to paint all houses?
- [0265]
[0265] - H - Paint House II -
[Python]
[CPP] -
[Video] -
[DP]
- same as [1289]
[0266] - E - Palindrome Permutation -
[Python]
[CPP] -
[Video] -
[Palindrome]
[0269] - H - Alien Dictionary -
[Python]
[CPP] -
[Video] -
[topology sort][classic]
[0273] - H - Integer to English Words -
[Python]
[CPP] -
[Video] -
[Recursive]
[0276] - M - Paint Fence -
[Python]
[CPP] -
[Video] -
[DP]
[0287] - M - Find the Duplicate Number -
[Python]
[CPP] -
[Video] -
[Indexing Sort][Binary Search]
- Indexing Sort: O(N)
- Binary Search: Nlog(N)
[0295] - H - Find Median from Data Stream -
[Python]
[CPP] -
[Video] -
[heap][SortedList][Medium]
[0297] - H - Serialize and Deserialize Binary Tree -
[Python]
[CPP] -
[Video] -
[Tree Serialization][classic]
[0300] - M - Longest Increasing Subsequence -
[Python]
[CPP] -
[Video] -
[sub-sequence][DP][classic][DP Type II]
- DP Bottom-up: O(N^2)
- Binary Search: Nlog(N)
- DP Top-Down(Cache): MLE
- DP Top-Down:
- Using 2D-array is more efficient than using dictionary
[0301] - H - Remove Invalid Parentheses -
[Python]
[CPP] -
[Video] -
[Parentheses][Search in an array]
- review search in an array
- DFS: pruning/eliminate duplication/memo
[0307] - M - Range Sum Query - Mutable -
[Python]
[CPP] -
[video-Binary Index Tree] -
[Video-segment tree] -
[Segment Tree][classic][Binary Index Tree]
- Segment Tree Intro/Classic
- Binary Index Tree [template]
- [python solution]
- [303]
- [315]
[0309] - M - Best Time to Buy and Sell Stock with Cooldown -
[Python]
[CPP] -
[Video] -
[DP]
[0315] - H - Count of Smaller Numbers After Self -
[Python]
[CPP] -
[Video] -
[Divide and Conquer]
[0324] - M Wiggle Sort II -
[Python]
[CPP] -
[Video] -
[Quick Select]
[0327] - H - Count of Range Sum -
[Python]
[CPP] -
[Video] -
[Divide and Conquer]
[0332] - H - Reconstruct Itinerary -
[Python]
[CPP] -
[Video] -
[DFS][Eulerian Path]
- Given an Eulerian Path, construct the Eulerian path
- graph with list (adjacency list) to maintain lexical order
- how to reconstruct graph path with lexical order
[0341] - M - Flatten Nested List Iterator -
[Python]
[CPP] -
[Video] -
[Stack][Generator]
[0347] - M - Top K Frequent Elements -
[Python]
[CPP] -
[video1]
[Video2] -
[Quick Select]
[0348] - M - Design Tic-Tac-Toe -
[Python]
[CPP] -
[Video] -
[Design]
[0355] - M - Design Twitter -
[Python]
[CPP] -
[Video] -
[Design]
- pull or push design
- push: new follower won't get history post
- pull, follower only keep top 10 records
[0358 - H - Rearrange String k Distance Apart](https://leetcode.com/problems/rearrange-string-k-distance-apart/description/) -
[Python]
[CPP] -
[Video] -
[Arrangement with Stride][Greedy][classic]
[0368] - M - Largest Divisible Subset -
[Python]
[CPP] -
[Video] -
[DP]
- all pairs are divisible in a set -> we do not need to try all pairs, just sort and confirm nums[ii]%nums[jj]==0 for ii=jj+1
- when dealing with subset on a single array and N^2 is the decided algorithm -> sorting the original array a lot of time has benefits
- DP output the path -> record the prev for tracing back
- avoid recording the whole path. try recording prev and trace back
//c++ max of vector elements
int mx_sz = *(std::max_element(dp.begin(), dp.end()));[0370] - M - Range Addition -
[Python]
[CPP] -
[Video] -
[Intervals][Segment Tree][Range Addition]
- [1109]
[0373] - M - Find K Pairs with Smallest Sums -
[Python]
[CPP] -
[Video] -
[Binary Search][TopK]
- the initial value of ans is special
[0376] - M - Wiggle Subsequence -
[Python]
[CPP] -
[Video-sol] -
[DP][Greedy]
Greedy Solution: find number of turning points
[0378] - M - Kth Smallest Element in a Sorted Matrix -
[Python]
[CPP] -
[Video] -
[Find K0th Element][Top K][Binary Search]
- [0240] Search a 2D Matrix II (how to traverse matrix with sorted row/col)
- [0373] (similar question)
- [2040]
[0380] - M - Insert Delete GetRandom O(1) -
[Python]
[CPP] -
[Video] -
[Design]
[0381] - H - Insert Delete GetRandom O(1) - Duplicates allowed -
[Python]
[CPP] -
[Video] -
[Design]
[0387] - E - First Unique Character in a String -
[Python]
[CPP] -
[Video] -
[MISC]
[0394] - M - Decode String -
[Python]
[CPP] -
[Video] -
[stack]
- review basic calculators
[0402] - M - Remove K Digits -
[Python]
[CPP] -
[Video] -
[Stack][monotonic stack][classic][form smallest sequence]
- How to make a list of number monotonically increasing
[[0432] - H - All Oone Data Structure](https://leetcode.com/problems/all-oone-data-structure/description/) - [[Python]]() [[CPP]](https://github.com/wisdompeak/LeetCode/tree/master/Design/432.All-O-one-Data-Structure) - [[Video]](https://www.youtube.com/watch?v=1TK2a26zU6I) - [Design][LinkedList`]
- O(1) key/value update
- O(1) retrieving any key of min/max frequency
- how to maintain frequency order to look back key
- maintain min/max and order of frequency -> list
- maintain medium -> two heap
[0435] - M - Non-overlapping Intervals -
[Python]
[CPP] -
[Video] -
[interval][classic]
- Sort by Starting Point or Ending Point?
[0460 - H - LFU Cache](https://leetcode.com/problems/lfu-cache/description/) -
[Python]
[CPP] -
[Video] -
[Design][OrderedDict]
- File system is Trie
- removing kv from OrderedDict:
# removing a key from OrderedDict * val=self.f2kv[freq].pop(key) # removing the front/back element from OrderedDict * min_k, min_v=self.f2kv[self.min_freq].popitem(last=False)
[0472] - H - Concatenated Words -
[Python]
[CPP] -
[Video] -
[Trie]
- word break (139, 140)
- memo (lru_cache) is the best friend of DFS
[0487] - M - Max Consecutive Ones II -
[Python]
[CPP] -
[Video] -
[DP]
[0493] - H - Reverse Pairs -
[Python]
[CPP] -
[Video] -
[Divide Conquer]
- divide and conquer - sol1
- Python: Sorted List - sol2
[0494] - M - Target Sum -
[Python]
[CPP] -
[Video] -
[DP]
- [2518]
[0495] - E - Teemo Attacking -
[Python]
[CPP] -
[Video] -
[Intervals]
[0500] - H - desc -
[Python]
[CPP] -
[Video] -
[Patterns]
[0535] - M - Encode and Decode TinyURL -
[Python]
[CPP] -
[Video] -
[Design]
[0543] - E - Diameter of Binary Tree -
[Python]
[CPP] -
[Video] -
[Tree]
[0547] - M - Number of Provinces -
[Python]
[CPP] -
[Video] -
[Union Find][classic]
[0560] - M - Subarray Sum Equals K -
[Python]
[CPP] -
[Video] -
[Patterns]
[0581] - M - Shortest Unsorted Continuous Subarray -
[Python]
[CPP] -
[Video] -
[Greedy][Monotonic stack]
[0583] - M - Delete Operation for Two Strings -
[Python]
[CPP] -
[Video] -
[DP]
[0588] - H - Design In-Memory File System
-
[Python]
[CPP] -
[Video] -
[Design][Trie]
[0620] - E - Not Boring Movies -
[Python]
[CPP] -
[SQL]
- sql mod
[0596] - E - Big Countries -
[Python]
[CPP] -
[Video] -
[SQL][`Pandas]
[0621] - M - Task Scheduler -
[Python]
[CPP] -
[Video] -
[Intervals][Sweep Line][Arrangement with Stride][Greedy]
- 0358
- Simulation (using heap)
- O(N) solution for arrangement with stride:
[0632] - H - Smallest Range Covering Elements from K Lists -
[Python]
[CPP] -
[Video] -
[heap]
- max with custom key for sorting
- how to manage max value in a min_heap
[0636] - M - Exclusive Time of Functions -
[Python]
[CPP] -
[Video] -
[Stack]
[0642] - H - Design Search Autocomplete System -
[Python]
[CPP] -
[Video] -
[Trie][Design]
- [1268]
- Given a dictionary for lookup -> Trie
- Sort by (freq, lexical order), but Trie at best is lexical order only -> need sorting @ end for final output
- preserve current iter and current user input and use DFS to find all in scope words[0652] - M - Find Duplicate Subtrees -
[Python]
[CPP] -
[Video] -
[Tree][Tree Serialize]
- [1948]
[0668] - H - Kth Smallest Number in Multiplication Table -
[Python]
[CPP] -
[Video] -
[Binary Search][Sorted Matrix]
- Sorted matrix
[0673] - M - Number of Longest Increasing Subsequence -
[Python]
[CPP] -
[Video] -
[DP]
- [0300]: longest increasing subsequence
# defaultdict of value=1 int
idx2cnt = collections.defaultdict(lambda: 1)[0691] - H - Stickers to Spell Word -
[Python]
[CPP] -
[Video] -
[State Compression]
- cf: word break
[0692] - M - Top K Frequent Words -
[Python]
[CPP] -
[Video] -
[Quick Select][heap][bucket sort]
[0703] - E - Kth Largest Element in a Stream -
[Python]
[CPP] -
[Video] -
[TopK]
[0719] - H - Find K-th Smallest Pair Distance -
[Python]
[CPP] -
[Video] -
[TopK][Binary Search][Two Dimentional TopK]
- How to apply binary search with paired distance
- If we decided NlogN as time complexity -> sort if you can.
- Can you do this in Quick-select?
[0759] - H - Employee Free Time -
[Python]
[CPP] -
[Video] -
[Sweep Line]
[0763] - M - Partition Labels -
[Python]
[CPP] -
[Video] -
[Intervals]
[0767] - M - Reorganize String -
[Python]
[CPP] -
[Video] -
[TopK][Greedy][arrangement with stride]
- [1054]
- [1953]
[0772] - H - Basic Calculator III -
[Python]
[CPP] -
[Video] -
[String Manipulation][calculator]
[0815] - H - Bus Routes -
[Python]
[CPP] -
[Video] -
[BFS]
- BFS variation
[0828] - H - Count Unique Characters of All Substrings of a Given String -
[Python]
[CPP] -
[Video] -
[Count Subarray by Element]
- [2262] VS [828]: unique char VS distinct char in subarray
- unique: ignore chars with duplicates
- distinct: duplicate chars count as 1
[0843] - H - Guess the Word -
[Python]
[CPP] -
[Video] -
[Video 2]
[Design][Others]
[0871] - H - Minimum Number of Refueling Stops -
[Python]
[CPP] -
[Video] -
[Greedy]
[0875] - M - Koko Eating Bananas -
[Python]
[CPP] -
[Video] -
[Binary Search]
[0881] - M - Boats to Save People -
[Python]
[CPP] -
[Video] -
[Greedy]
[0895] - H - Maximum Frequency Stack -
[Python]
[CPP] -
[Video] -
[Design][Stack]
[0921] - M - Minimum Add to Make Parentheses Valid -
[Python]
[CPP] -
[Video] -
[Parentheses][Greedy]
[0931] - M - Minimum Falling Path Sum -
[Python]
[CPP] -
[Video] -
[DP]
[0937] - M - Reorder Data in Log Files -
[Python]
[CPP] -
[Video] -
[Sorting]
[0946] - M - Validate Stack Sequences -
[Python]
[CPP] -
[video] -
[Stack]
- How to validate a stack sequence? -> use stack to validate stack sequence
1. keep adding element to stk from pushed until stk[-1]==popped[jj]
2. keep popping until stk is empty or jj >= len(popped)
3. return not stk[0968] - H - Binary Tree Cameras -
[Python]
[CPP] -
[Video] -
[Tree][DP][Greedy]
- Tree with DP
[0973] - M - K Closest Points to Origin -
[Python]
[CPP] -
[Video] -
[Quick]
[0986] - M - Interval List Intersections -
[Python]
[CPP] -
[Video] -
[Intervals]
[0990] - M - Satisfiability of Equality Equations - [Python - UnionFind]
[Python - DFS]
[CPP] -
[Video-UnionFind 1]
[Video-UnionFind 2]
[Video-BFS] -
[BFS] [Union Find]
- [2307]
[0995] - H - Minimum Number of K Consecutive Bit Flips -
[Python]
[CPP] -
[Video] -
[sweep line][range addition]
[1000] - H - desc -
[Python]
[CPP] -
[Video] -
[Patterns]
[1020] - M - Number of Enclaves -
[Python]
[CPP] -
[Video] -
[DFS]
- [1254]
[1024] - M - Video Stitching -
[Python]
[CPP] -
[Video] -
[Greedy]
[1028] - H - Recover a Tree From Preorder Traversal -
[Python]
[CPP] -
[Video] -
[Tree]
[1029] - M - Two City Scheduling -
[Python]
[CPP] -
[Video] -
[Greedy]
[1035] - M - Uncrossed Lines -
[Python]
[CPP] -
[Video] -
[DP]
[1043] - M - Partition Array for Maximum Sum -
[Python]
[CPP] -
[Video] -
[DP]
- same as [1105]
- vs [1959]
[1044] - H - Longest Duplicate Substring -
[Python]
[CPP] -
[Video] -
[rolling hash][Binary Search][二哈哈希]
- DP: dp[i][j]= (s[i]==s[j])? dp[i-1][j-1]+1 ans = max(dp[i][j], i=0,...n, j=0,...,n)
[1049] - M - Last Stone Weight II -
[Python]
[CPP] -
[Video] -
[DP][0/1 Hacksack]
- 穷举法 （exhaustive method)
[1054] - M - Distant Barcodes -
[Python]
[CPP] -
[Video] -
[Greedy][arrangement with Stride]
- 0358
- [0767]
[1092] - H - Shortest Common Supersequence -
[Python]
[CPP] -
[Video] -
[DP][classic]
- DP returning path
[1105] - M - Filling Bookcase Shelves -
[Python]
[CPP] -
[Video] -
[DP]
[1109] - M - Corporate Flight Bookings -
[Python]
[CPP] -
[Video] -
[Sweep Line][Range Addition][Diff Array]
[1143] - M - Longest Common Subsequence -
[Python]
[CPP] -
[Video] -
[DP][classic]
[1151] - M - Minimum Swaps to Group All 1s Together -
[Python]
[CPP] -
[Video] -
[Sliding Window]
- [idiom]: presum template
[1172] - H - Dinner Plate Stacks -
[Python]
[CPP] -
[Video] -
[Design]
- 0460 LFU
[1186] - M - Maximum Subarray Sum with One Deletion -
[Python]
[CPP] -
[Video] -
[DP]
[1203] - H - Sort Items by Groups Respecting Dependencies -
[Python]
[CPP] -
[Video] -
[Topology Sort]
[1207] - E - Unique Number of Occurrences -
[Python]
[CPP] -
[Video] -
[Hash]
[1235] - H - Maximum Profit in Job Scheduling -
[Python]
[CPP] -
[Video] -
[DP][Greedy]
- [435] From all the overlapping intervals, we pick the 1st interval (sorted by end-time)(least overlapping with future intervals). Greedy strategy
- [1235] for Max Profit, we cannot simply pick the first one (least overlapping) as we are trying to max(profit)
[1245] - M - Tree Diameter -
[Python]
[CPP] -
[Video] -
[Patterns]
[1249] - M - Minimum Remove to Make Valid Parentheses -
[Python]
[CPP] -
[Video] -
[stack][Greedy][parentheses]
[1251] - E - Average Selling Price -
[Python]
[CPP] -
[Video] -
[SQL]
- join with between, SQL between
- SQL round
- Pandas sort_values
- pandas merge_asof
[1254] - M - Number of Closed Islands -
[Python]
[CPP] -
[Video] -
[DFS]
Islands
- [0200]
- [1020]
[1268] - M - Search Suggestions System -
[Python]
[CPP] -
[Video] -
[Trie][binary search]
- [642]
- search suggestion sort lexically[1278] - H - Palindrome Partitioning III -
[Python]
[CPP] -
[Video] -
[DP]
[1289] - H - Minimum Falling Path Sum II -
[Python]
[CPP] -
[Video] -
[DP]
- [0256]: paint house I
- [0265]: Paint house II -- review this python code see how to share a loop
- [0931]
[1293] - H - Shortest Path in a Grid with Obstacles Elimination -
[Python]
[CPP] -
[Video] -
[BFS][BFS Variation]
[1326] - H - Minimum Number of Taps to Open to Water a Garden -
[Python]
[CPP] -
[Video] -
[Greedy][Interval]
- this is intervals
- [1024]
[1352] - M - Product of the Last K Numbers -
[Python]
[CPP] -
[Video] -
[Design]
- preprod, how to handle zero
[1360] - E - Number of Days Between Two Dates -
[Python]
[CPP] -
[Video] -
[MISC]
[1372] - M - Longest ZigZag Path in a Binary Tree -
[Python]
[CPP] -
[Video] -
[binary Tree][recursion]
[1381] - M - Design a Stack With Increment Operation -
[Python]
[CPP] -
[Video] -
[Design]
- application of "range addition"
- [1109]
[1473] - M - Paint House III -
[Python]
[CPP] -
[Video] -
[DP]
- [1959]
[1431] - E - Kids With the Greatest Number of Candies -
[Python]
[CPP] -
[Video] -
[Patterns]
[1492] - M - The Kth Factor of n -
[Python]
[CPP] -
[Video] -
[Patterns]
[1498] - M - Number of Subsequences That Satisfy the Given Sum Condition -
[Python]
[CPP] -
[Video] -
[Two Pointer][Count Subarray by Element]
- subsequence but we can sort
- if we need to constanly recalc pow -> precalc into dictionary
- when dealing with min-max pair: a. ii is min, find max (two pointers) -> O(N) b. ii is max. min is all from the right
- why [2681] choose ii as max but [1498] choose ii as min?
- Please try solve this with ii being the max and min.
- Before coding, consider a. ii is max VS ii is min b. ii from left-to-right VS ii from right-to-left => some options is just easier than others
[1500] - H - desc -
[Python]
[CPP] -
[Video] -
[Patterns]
[1578] - M - Minimum Time to Make Rope Colorful -
[Python]
[CPP] -
[Video] -
[Greedy]
[1591] - H - Strange Printer II -
[Python]
[CPP] -
[Video] -
[Topology Sort]
[1622] - H - Fancy Sequence -
[Python]
[CPP] -
[Video] -
[Design]
- 逆源 (inverse)
[1642] - M - Furthest Building You Can Reach -
[Python]
[CPP] -
[Video] -
[PriorityQueue][Greedy]
[1649] - H - Create Sorted Array through Instructions -
[Python]
[CPP] -
[Video] -
[Video-Segment Tree]
[Divide Conquer][BIT][Segment Tree][PBDS]
- [0315]
[1650] - M - Lowest Common Ancestor of a Binary Tree III -
[Python]
[CPP] -
[Video] -
[LCA]
[1670] - M - Design Front Middle Back Queue -
[Python]
[CPP] -
[Video] -
[Design]
[1676] - M - Lowest Common Ancestor of a Binary Tree IV
-
[Python]
[CPP] -
[Video] -
[Tree][LCA]
[1705] - E - Project Employees I -
[Python]
[CPP] -
[Video] -
[SQL]
- pandas: group by
[1723] - H - Find Minimum Time to Finish All Jobs -
[Python]
[CPP] -
[Video] -
[DFS][DP][狀態壓縮 DP][Binary Search]
> Take aways
* DFS pruning
* sort the search order so it's easier to trigger threshold and being pruned early
* leveraging the fact that assigning a new job to any empty worker is the same, no need to try over and over again on same situation(Try to assign those that is easier to trigger threshold to avoid unnecessary probing/searching)
* DFS memo
* Binary search with state compression DP
* State compression: How to iterate all subsets
* How to represent states via Bits- time complexity: k*3^N (explained in other video)
> Similar Q:
- [1986]
- [2323]
- [2589][1723] VS [1986] >
[1723]
+ N tasks assign to k workers
+ tasks[ii]: the required time to complete task_ii
=> min time of max worker_time to complete all tasks
+ required min time unknown
assuming N=4
state: 1111 meaning to complete all 4 jobs
1011 meaning to complete 3 jobs (with 2nd job)
dp[ii][state]: min time required for max_time a worker takes for all workers to finish all jobs in the state
# initial state
* dp[0][0]=0
* all others are math.inf
* dp[ii][jj] = min(dp[ii][jj], max(dp[ii-1][state-subset], time[subset]))
[1986]
- N tasks assign to 1 worker with constrain session_time
=> min number of session required to complete all tasks
+ number of sessions unknown
* state: 1111 meaning to complete all 4 jobs
* 1011 meaning to complete 3 jobs (with 2nd job)
* dp[state]: min number of sessions required to finish all jobs defined in the state
# initial state: identify those state that could be finished in 1 session, all others are math.inf
* dp[state] = min(dp[state], dp[subset]+dp[state-subset])
# how to traverse all subset of a bit
subset=state
while subset > 0:
# to something on the subset
subset=(subset-1)&state[1840] - H - Maximum Building Height -
[Python]
[CPP] -
[Video] -
[Greedy]
- [135]
[1857] - H - Largest Color Value in a Directed Graph -
[Python]
[CPP] -
[Video] -
[Topology Sort]
- when you see anything that is represented in lower case english letters, think of can we try all 26 letters on same calc
- if you need to detect cycle -> topology sort (or review DFS detect cycle, cf. [207])
- we cannot rely on parent's color count as we might reach this child from diff depth. so each node's color count should be the max of all reachable path, not just from previous level
mxf=-N # since we could return -1, be careful on the initial value of the return var
for a_color in colors_set: # for each color# defaultdict of defaultdict
defaultdict(lambda: defaultdict(int))[1918] - M - Kth Smallest Subarray Sum -
[Python]
[CPP] -
[Video] -
[Binary Search]
[1942] - M - The kth Factor of n -
[Python]
[CPP] -
[Video] -
[Patterns]
[1953] - M - Maximum Number of Weeks for Which You Can Work -
[Python]
[CPP] -
[Video] -
[Arrangement with Stride][Greedy]
[1959] - M - Minimum Total Space WWasted With K Resizing Operations -
[Python]
[CPP] -
[Video] -
[DP]
- Type II DP Basic
- todo-not todo with with max k times
- [1043]
- [1105]
[1986] - M - Minimum Number of Work Sessions to Finish the Tasks -
[Python]
[CPP] -
[Video] -
[DP]
> 枚举集合子集
- [0691]
- [1494]
- [1655][2000] - H - Sequentially Ordinal Rank Tracker -
[Python]
[CPP] -
[Video] -
[Patterns]
[2040] - H - Kth Smallest Product of Two Sorted Arrays -
[Python]
[CPP] -
[Video] -
[Binary Search][Binary Search by Value]
- [1918]
- binary serach kth product, sum, diff from two sorted list
- when processing pair from two arrays. fix one and binary_search (bisect) the other. This only requires 2nd array sorted. we do not need first array sorted. what a waste? (NlogN)
- O(N) - two pointers solution (cf readme link)
[2102] - H - Sequentially Ordinal Rank Tracker -
[Python]
[CPP] -
[Video] -
[Heap]
- PBDS (平板电视)
- real-time sorting VS random access cannot co-exist
- Python sortedList (sorted_list, sorted list, SortedList)
[2104] - M - Sum of Subarray Ranges -
[Python]
[CPP] -
[Video] -
[Monotonic Stack]
- monotonic one pass solution
- [907]
- [1856]
[2163] - H - Minimum Difference in Sums After Removal of Elements -
[Python]
[CPP] -
[Video] -
[Three-pass]
- when you see the result is asking for the relation btn left and rigth -> do left and right and 3rd pass output result
[2166] - M - Design Bitset -
[Python]
[CPP] -
[Video] -
[Design]
[2193] - H - Minimum Number of Moves to Make Palindrome -
[Python]
[CPP] -
[Video] -
[Greedy][Reverse Pair]
- [0493]: reverse pairs for solution 2
[2222] - M - Number of Ways to Select Buildings -
[Python]
[CPP] -
[Video] -
[DP]
- Number of Ways to Select something.
- Number of Ways to climb stairs.
- Number of Ways to achieve some score
- Number of Ways to make some amount from coins
[2227] - H - Encrypt and Decrypt Strings -
[Python]
[CPP] -
[Video] -
[Design]
[2233] - M - Maximum Product After K Increments -
[Python]
[CPP] -
[Video] -
[Math][Binary Search][Smear Top Elements][Greedy]
- [0343]: understand the diff 2233 vs 0343
[2234] - H - Maximum Total Beauty of the Gardens -
[Python]
[CPP] -
[Video] -
[Math][Binary Search][Smear Top Elements][Greedy]
[2254] - E - Design Video Sharing Platform -
[Python]
[CPP] -
[Video] -
[Design]
[2262] - H - Total Appeal of A String -
[Python]
[CPP] -
[Video] -
[Count Subarray by Element]
[2268] - M - Minimum Number of Keypresses -
[Python] -
[Sort]
[2272] - H - Substring With Largest Variance -
[Python] -
[Video]
[Max Subarray][Modified Kadane]
- diff of freq of two chars in a substring is equivalent to set a=1, b=-1 and all others 0 and sum
- max subarray sum -> Kadane
- variation of kadane: requiring two elements (subarray need to contain both a and b)
- If we need to try all combinations, consider only 1 combination and repeat same thing for all others
- When finding max something of all subarraies, we might only need to consider the whole array as any subarray won't qualify
[2277] - E - Closest Node to Path in Tree -
[Python]
[CPP] -
[Video] -
[Video-2]
[Patterns]
- when you query a data structure, think of if any info that can be shared so we do not have to process from scratch on each query
- pre-process distance table matrix
- dist(start, end)= 1 + dist(j, end) where j is start's child
- Tree has no cycle.
- find path from A-B in graph (BFS/DFS)
[2281] - H - Sum of Total Strength of Wizards
-
[Python]
[CPP] -
[Video] -
[Video - deprecated] -
[Count Subarray By Element][Monotonic Stack]
- presum: insert dummy header
- [907] [
Aggregate Subarray by element]
[2296] - H - Design a Text Editor -
[Python]
[CPP] -
[Video] -
[Design][Linked List]
- what data structure supports easy insert, delete
- list solution
- stack solution
[2297] - M - Jump Game VIII -
[Python] -
[Video] -
[DP] [Monotonic Stack]
[2302] - H - Count Subarrays With Score Less Than K -
[Python]
[[CPP]] -
[Video] -
[Count Subarray By Element]
[2307] - H - Check for Contradictions in Equations -
[Python] -
[Video] -
[BFS/DFS][Union Find]
- [990] - BFS/Union Find
[2313] - H - Minimum Flips in Binary Tree to Get Result -
[Python]
[CPP] -
[Video] -
[Tree]
- Tree is about recurson (98%)
- DFS's best friend is memo
[2323] - M - Find Minimum Time to Finish All Jobs II -
[Python]
[CPP] -
[Video] -
[Greedy]
[2330] - M - Valid Palindrome IV -
[Python]
[CPP] -
[Video] -
[Palindrome]
[2334] - H - Subarray With Elements Greater Than Varying Threshold -
[Python]
[CPP] -
[Video] -
[Monotonic Stack]
- [42]
- [84]
[2340] - M - Minimum Adjacent Swaps to Make a Valid Array -
[Python]
[CPP] -
[Video] -
[Patterns]
[2345] - M - Finding the Number of Visible Mountains -
[Python]
[CPP] -
[Video] -
[Intervals]
[2355] - H - Maximum Number of Books You Can Take -
[Python]
[CPP] -
[Video] -
[Video] -
[DP][Monotonic Stack][Monotonic Stack Various]
- whenever maintaining a monotonic sequence relationship -> how to use monotonic stack?
- monotonic stack variation: smaller per some formula
- previous smaller with condition.
- Monotonic stack application with condition
[2371] - E - Minimize Maximum Value in a Grid -
[Python]
[CPP] -
[Video] -
[Greedy]
[2386] - H - Find the K-Sum of an Array -
[Python]
[CPP] -
[Video] -
[Priority Queue]
- the subsequence of kth sum
[2405] - M - Optimal Partition of String -
[Python]
[CPP] -
[Video] -
[Patterns]
[2408] - M - Design SQL -
[Python]
[CPP] -
[Video] -
[Design]
[2422] - M - Merge Operations to Turn Array Into a Palindrome -
[Python]
[CPP] -
[Video] -
[Two Pointers][Greedy]
[2439] - M - Minimize Maximum of Array -
[Python]
[CPP] -
[Video] -
[Binary Search]
[2459] - E - Sort Array by Moving Items to Empty Space -
[Python]
[CPP] -
[Video] -
[Union Find][Index Sort][Greedy]
- how to think when dealing with circle
* sort array
* nums of size n
* nums[ii] in (0, n-1)
* N=10^5 -> nlogn
-> index sort
* min operations -> DP, Greedy, Binary[2461] - M - Maximum Sum of Distinct Subarrays With Length K -
[Python]
[CPP] -
[Video] -
[Two Pointers][Sliding Window]
[2486] - M - Append Characters to String to Make Subsequence -
[Python]
[CPP] -
[Video] -
[Patterns]
[2500] - H - desc -
[Python]
[CPP] -
[Video] -
[Patterns]
[2510] - M - Check if There is a Path With Equal Number of 0's And 1's -
[Python]
[CPP] -
[Video - Iteration] -
[Video - Recursion + Cache]
[DFS][BFS]
- How to use @cache
- print(check.cache_info())
- check.cache_clear()
- BFS by iteration: how to use memo in BFS? if visited, do not add it's children into the queue
- DFS by recursion
- How memo/cache can prune the search path in BFS
- How memo can reduce duplicate search
[2518] - H - Number of Great Partitions -
[Python]
[CPP] -
[Video] -
[DP]
[2519] - H - Count the Number of K-Big Indices -
[Python]
[CPP] -
[Video-Binary Search] -
[Video-heap]
[Binary Search][Heap]
- when we need to consider both left and right, we can first focus on left as right is just the reverse of it
- To find the rank of each element -> binary search (bisect into an new array)
- To find how many elements before current index that is greater or lesser -> use heap maintaining top k
- how to maintain running top k
[2528] - H - Maximize the Minimum Powered City -
[Python]
[CPP] -
[Video] -
[Binary Search]
[2534] - H - Time Take to Cross the Door -
[Python]
[CPP] -
[Video] -
[Simulation]
[2563] -M - Count the Number of Fair Pairs -
[Python]
[CPP v1]
[CPP v2] -
[Video] -
[Binary Search]
[2565] - H - Subsequence With the Minimum Score -
[Python]
[CPP] -
[Video] -
[3 pass][Binary Search][Two Pointers][Greedy]
[2589] - H - Minimum Time to Complete All Tasks -
[Python]
[CPP] -
[Video] -
[Greedy][Interval]
- Merge overlapping intervals with constrain (start, end) of the duration
- [1723]
[2597] - M - The Number of Beautiful Subsets -
[Python]
[CPP-DFS] -
[CPP-DP] -
[Video] -
[DP]
- [2638]
[2638] - M - Count the Number of K-Free Subsets -
[Python]
[CPP] -
[Video] -
[DP]
- when you want to group or take subset with members has no diff=k -> group by mod k
- when you group by mod k -> any members from two diff group the diff cannot be k
- whether or not you can take a number into subset depends on the diff with prev num -> house robber problem
- what's the difference btn "(90): subset II" and "(198): House Robber"
- no duplicate meaning no difference picking any of the duplicate
- two elements cannot have some kind of relationship -> need to consider pick A or pick B -> when making decisions -> DP/Greedy
- count subset from an array with constrains
1. [0078]: Array of unique numbers -> All Subsets
2. [0090]: Array of duplicate numbers -> All Subsets without duplicate
3. bruteforce solution (this might not even a correct strategy.)
4. apply [0090] strategy TLE
5. House Robber
6. group by mod
7. 2597 a similar question- [2597]
[2681] - H - Power of Heroes -
[Python]
[CPP] -
[Video] -
[Count Subarray by Element]
- group means subset, we can sort
- Whenever we do something btn min/max for subsequence/subset, sort the original
- [1498]
[2866] - M - Beautiful Towers II -
[Python]
[CPP] -
[Video] -
[Monotonic Stack]
- [0084]
[2867] - H - Count Valid Paths in a Tree
-
[Python]
[CPP] -
[Video] -
[Union Find][Prime Number]
[2877] - E - Create a DataFrame from List -
[Python]
[CPP] -
[Video] -
[pandas]
[2878] - E - Get the Size of a DataFrame -
[Python]
[CPP] -
[Video] -
[pandas]
[2996] - E - Smallest Missing Integer Greater Than Sequential Prefix Sum -
[Python]
[CPP] -
[Video] -
[MISC]
[2997] - M - Minimum Number of Operations to Make Array XOR Equal to K -
[Python]
[CPP] -
[Video] -
[BITwise Manipulation]
[2998] - M - Minimum Number of Operations to Make X and Y Equal -
[Python]
[CPP] -
[Video] -
[Patterns]
[3000] - H - Maximum Area of Longest Diagonal Rectangle -
[Python]
[CPP] -
[Video] -
[Sorting]
[3001] - M - Minimum Moves to Capture The Queen -
[Python]
[CPP] -
[Video] -
[MISC]
[3002] - M - Maximum Size of a Set After Removals -
[Python]
[CPP] -
[Video] -
[Patterns]
[3005] - E - Count Elements With Maximum Frequency -
[Python]
[CPP] -
[Video] -
[Analysis]
[3006] - M - Find Beautiful Indices in the Given Array I -
[Python]
[CPP] -
[Video] -
[Patterns]
[3007] - M - Maximum Number That Sum of the Prices Is Less Than or Equal to K -
[Python]
[CPP] -
[Video] -
[Patterns]
[3008] - H - Find Beautiful Indices in the Given Array II -
[Python]
[CPP] -
[Video] -
[Patterns]
[] - H - desc -
[Python]
[CPP] -
[Video] -
[Patterns]
[] - M - desc -
[Python]
[CPP] -
[Video] -
[Patterns]
[] - E - desc -
[Python]
[CPP] -
[Video] -
[Patterns]
to link image
