owned this note
owned this note
Published
Linked with GitHub
leetcode
===
- DNF list
- 715, 685, 260, 808, 321, 803, 44, 555, 664, 407, 164, 324, 715, 730, 336, 363, 471, 932, 406(nlogn), 936
- Notations
- DNF: did not finish by my own
- buggy: multiple times of debugging
- imple: implementation. trivial solution like scan or string manipulation
- H:hard, M: medium, E: easy
- g4g: geeksforgeeks, lt: lintcode
- interview
- 62, 843, 890(8), 489, 855, 853, 857, 750, 843
- 11/07~11/10
- 940. Distinct Subsequences II
- DP
- (lt)458E. Last Position of Target
- {buggy} bin search
- (lt)1541H. Put Box
- DP
- (lt)825H. Bus Station
- BFS
- (lt)1555H. Flower Problem
- union find set
- (lt)1538M. Card Game II
- search
- (lt)903M. Range Addition
- {buggy}. imple
- (lt)1539M. Flipped the Pixel
- imple
- (lt)1542M. NextTime Norepeat
- imple
- (lt)1543M. Unique Path IV
- DP
- (lt)1545M. Last Closest Time
- imple
- (lt)1554M. LastTime Norepeat
- {buggy} corner-case.
- (lt)1086E. Repeated String Match
- imple
- 11/06
- (lt)315H. Count of Smaller Numbers After Self
- (10min). mergesort
- (lt)1576H. Optimal Match
- (60min). bipartite max perfect matching. hungarian algorithm with weights (dual value+tight edge+augmentation path+delta). O(MN^2)
- (lt)1641M. Max Remove Order
- (13min). Union-find set
- (lt)1646M. CheckWords
- (15min). BFS
- (lt)1640H. Duplicates Digits
- (15min). DP. add another dimension if have to handle different cases
- 936H. Stamping The Sequence
- greedy simulation
- 11/04
- (lt)1640H. Duplicates Digits
- (35min+). {DNF} DP.
- use top-bottom search when get stuck.
- (lt)109M. Triangle
- (4min). DP
- (lt)1642M. Query String
- (10min). pure brutal force. meaningless problem.
- (lt)1643M. Pick Fruits
- (5min). sliding window
- (lt)1634M. Secret Word
- (8min). mapping count.
- (lt)1644M. Plane Maximum Rectangle
- (10min). hash.
- (lt)1633E. Strings That Satisfies The Condition
- (5min). imple
- (lt)1645E. Least Subsequences
- (6min). Bin-search
- `bisect_left: arr[lo:i]<val arr[i:hi]>=val`
- (lt)1580M. Transition String
- (20min) {buggy}. hash. find loop
- (g4g)E. Check if Tree is Isomorphic
- (5min). recursive
- 659M. Split Array into Consecutive Subsequences
- (12min). queue+hash. dont overkill, just focus on the essential property.
- {DNF}. O(1) space.
- 11/03
- weekly contest
- 936H. Stamping The Sequence
- {DNF}
- 935M. Knight Dialer
- DP
- 934M. Shortest Bridge
- BFS
- 933E. Number of Recent Calls
- queue
- 815M. Bus Routes
- {buggy}. BFS. remember to remove duplicated edge
- 750M. Number Of Corner Rectangles
- DP or hash-table
- 11/01~11/02
- 857H. Minimum Cost to Hire K Workers
- sort, heap
- 853M. Car Fleet
- greedy, sort
- 855M. Exam Room
- heap (override comparator `__lt__`)
- 489H. Robot Room Cleaner
- recursive
- 498M. Diagonal Traverse
- shifting
- 890M. Find and Replace Pattern
- mapping equality
- 843M. Guess the Word
- {DNF} Good problem. creative question.
- 62M. Unique Paths
- simple DP
- 685H. Redundant Connection II
- two in degree
- 684M. Redundant Connection
- union find set
- 399M. Evaluate Division
- DFS
- 760E. Find Anagram Mappings
- hash
- 326E. Power of Three
- mod trick
- 388M. Longest Absolute File Path
- stack
- 10/31
- 231E. Power of Two
- imple. corner cases
- 345E. Reverse Vowels of a String
- imple
- 421M. Maximum XOR of Two Numbers in an Array
- Trie
- 448M. Find All Numbers Disappeared in an Array
- use negation as hash
- 657E. Robot Return to Origin
- imple
- 316H. Remove Duplicate Letters
- hashset + recursion
- {DNF} stack
- 280M. Wiggle Sort
- imple
- 228M. Summary Ranges
- imple
- 463E. Island Perimeter
- imple
- 832E. Flipping an Image
- imple
- 208M. Implement Trie (Prefix Tree)
- Trie
- 66E. Plus One
- imple
- 218H. The Skyline Problem
- {buggy} overlapped boundary. merge
- 162M. Find Peak Element
- binary search
- 739M Daily Temperatures
- stack
- 10/29+10/30
- 735M. Asteroid Collision
- stack
- google
- 406M. Queue Reconstruction by Height
- sort and insert: O(N^2)
- {DNF} O(Nlogn): modified merge-sort
- {DNF} segtree?
- 140H. Word Break II
- DP
- 315H. Count of Smaller Numbers After Self
- divide and conquer
- bit
- 240M. Search a 2D Matrix II
- grid divide and conquer
- 295H. Find Median from Data Stream
- double heap
- 312H. Burst Balloons
- rangeDP
- 387E. First Unique Character in a String
- hash
- 10/28
- google:
- 341M. Flatten Nested List Iterator
- recursion. prefetch.
- 239H. Sliding Window Maximum
- deque. only maintain necessary elements.
- 535M. Encode and Decode TinyURL
- relevant hash (compression) vs irrelevant hash (key gen). System Design
- 155E. Min Stack
- stack
- 224H. Basic Calculator
- {buggy} imple
- 128H. Longest Consecutive Sequence
- hashing
- 50M. Pow(x, n)
- imple
- 173M. Binary Search Tree Iterator
- generator
- manual stack
- 289M. Game of Life
- mix information with different bits
- 54M. Spiral Matrix
- imple
- oneline (recursive)
- 22M. Generate Parentheses
- dfs
- 10/27
- Weekly contest
- 932M. Beautiful Array
- {DNF}. constructive answer
- 931M. Minimum Falling Path Sum
- DP.
- 930M. Binary Subarrays With Sum
- imple
- three pointer solution with O(1) space
- 929E. Unique Email Addresses
- hash
- 10/26
- google:
- 297H. Serialize and Deserialize Binary Tree
- encoding
- 31M. Next Permutation
- imple
- 139M. Word Break
- Trie.
- dp with hash.
- 253M. Meeting Rooms II
- heap.
- 17M. Letter Combinations of a Phone Number
- dfs
- 23H. Merge k Sorted Lists
- heap
- 10H. {buggy} Regular Expression Matching
- mem+dfs
- bugs:
- p_pos < m when s_pos >= n
- s_pos>=n, cannot read s[s_pos]
- check equality when *
- check s_pos < n when star == False
- 56M. Merge Intervals
- greedy
- 42H. Trapping Rain Water
- prefix-sum. S(N)=O(N)
- two pointers
- 20E. Valid Parentheses
- stack
- 200M. Number of Islands
- flood fill.
- -followup: partition, union-find set
- 4H. Median of Two Sorted Arrays
- binsearch
- 146H. LRU Cache
- dbl link list+hash
- 253M. Meeting Rooms II
- heap
- 10/25
- new:
- 4H. Median of Two Sorted Arrays
- binsearch. estimate the final state and binary search the answer
- review:
- 863M. All Nodes Distance K in Binary Tree
- recursion. make use of the return
- 307M. Range Sum Query - Mutable
- BIT. SegTree
- 285M. Inorder Successor in BST
- Morris. BST property
- 205E. Isomorphic Strings
- hash
- 10/22~10/23
- 363H. Max Sum of Rectangle No Larger Than K
- {DNF}. Binary search Tree
- 471H. Encode String with Shortest Length
- {DNF} recrusive. Cannot do that bottom to top.
- 727H. Minimum Window Subsequence
- DP. {buggy} `min` is slower than `else`
- 702M. Search in a Sorted Array of Unknown Size
- Bin search
- 215M. Kth Largest Element in an Array
- quick select
- 10/20
- 928H. Minimize Malware Spread II
- Dfs
- 927H. Three Equal Parts
- constructive
- 926M. Flip String to Monotone Increasing
- Prefix
- 925E. Long Pressed Name
- two pointers
- 336H. Palindrome Pairs
- Trie+Palidorme
- 10/19
- 532E. K-diff Pairs in an Array
- hash
- 295H. Find Median from Data Stream
- double heap
- 480H. Sliding Window Median
- a lazy remove heap design
- 826M. Most Profit Assigning Work
- binsearch. {buggy} notice lower cost might have higher reward
- 901M. Online Stock Span
- stack
- 100E. 100. Same Tree
- simple recursion
- 451M. Sort Characters By Frequency
- hash
- 10/18
- 830E. Positions of Large Groups
- simple imple
- 472H. Concatenated Words
- Trie. Passed with Python2 not PYthon3 (TLE).
- 170E. Two Sum III - Data structure design
- simple OOD
- 730H. Count Different Palindromic Subsequences
- {DNF}. range DP
- 519M. Random Flip Matrix
- hash, mapping design
- {buggy}. interesting problem
- 668H. Kth Smallest Number in Multiplication Table
- heap. O(Q\*log(N)), since Q is large, it will cause TLE.
- binsearch. O(log(Q)\*N). passed
- 10/17
- 517. Super Washing Machines
- {buggy}. debt counting
- can be simpler
- Google OA 2
- Google OA 1
- 630. Course Schedule III
- heap+greedy
- 10/14
- 316. Remove Duplicate Letters
- {buggy} hash+greedy
- 10/13 (pick one day)
- weekly contest
- 924 Minimize Malware Spread
- Union find+counting
- 923 3Sum With Multiplicity
- Math+hash
- Notice N<=3000 and 0<=a\[i\]<=100
- 922 Sort Array By Parity II
- simple sort
- two pointer
- 921 Minimum Add to Make Parentheses Valid
- stack
- 246. Strobogrammatic Number
- {buggy} two pointer
- 244. Shortest Word Distance II
- hash+two pointer
- 742. Closest Leaf in a Binary Tree
- onepass search
- 222. Count Complete Tree Nodes
- recursive
- 393. UTF-8 Validation
- simulation
- 282. Expression Add Operators
- {buggy} dfs
- 849. Maximize Distance to Closest Person
- prefix
- 10/12 (pick one day)
- 275. H-Index II
- {buggy} binsearch
- 117. Populating Next Right Pointers in Each Node II
- bfs
- 738. Monotone Increasing Digits
- constructive
- 875. Koko Eating Bananas
- binary search
- 424. Longest Repeating Character Replacement
- sliding window. greedy
- 544. Output Contest Matches
- simple string manipulation
- 645. Set Mismatch
- neg/pos hash
- 10/11
- 803. Bricks Falling When Hit
- brutal force. TLE with Python3, python2. pass with C++
- {DNF} reverse time+union-find
- 321. Create Maximum Number
- {DNF} Greedy+DP. dont be afraid of the complexity
- Passed with Python2 but not Python3.
- 10/10 (DNF review day)
- 406. Queue Reconstruction by Height
- constructive. O(N^2)
- has a shorter version with `insert`.
- 496. Next Greater Element I
- stack
- 632. Smallest Range
- heap.
- 446. Arithmetic Slices II - Subsequence
- DP with hash
- 260. Single Number III
- Get x1 ^ x2. Split into two conditions.
- 448. Find All Numbers Disappeared in an Array
- use negative/positive as hashing.
- 667. Beautiful Arrangement II
- constructive
- 371. Sum of Two Integers
- it can be solve with recursive code.
- Use C++. Since python don't have complementary
- 128. Longest Consecutive Sequence
- hash.
- 421. Maximum XOR of Two Numbers in an Array
- Trie. Notice time complexity is O(N\*#bits) = O(N\*32) = O(N)
- 898. Bitwise ORs of Subarrays
- brutal force. But the time complexity is tricky.
- 523. Continuous Subarray Sum
- hash. Notice the range of K
- O(N) with prefix_sum_hash. prefix_sum-prefix_sum = any range
- 42. Trapping Rain Water
- greedy+two pointer
- 683. K Empty Slots
- segtree. O(nlogn)
- bucket. O(n)
- 109. Convert Sorted List to Binary Search Tree
- two pointers + recursive
- 324. Wiggle Sort II
- O(N) to locate Kth smallest number
- 10/09
- 264. Ugly Number II
- heap+hash
- 3pointers (2ptr, 3ptr, 5ptr)
- idea: regrouping
- (x\*2,x\*3,x\*5),(y\*2,y\*3,y\*5)... -> (x\*2, y\*2,...), (x\*3, y\*3,...), (x\*5, y\*5,...)
- 845. Longest Mountain in Array
- Automata
- 787. Cheapest Flights Within K Stops
- DP
- 782. Transform to Chessboard
- constructive. good one.
- 210. Course Schedule II
- topological sort
- 332. Reconstruct Itinerary
- backtrack. {buggy} duplicated edges.
- 10/08
- (hackerrank) Consecutive Subsequences
- DP. number theory.
- Passed with C++ but TLE with Python3.
- 10/07
- [Lyft Level 5 Challenge 2018 - Elimination Round](http://codeforces.com/contest/1033)
- [1033D Divisors](http://codeforces.com/contest/1033/problem/D)
- {buggy} number theory, hash
- [1033C Permutation Game](http://codeforces.com/contest/1033/problem/C)
- max-min search, brutal force!
- [1033B Square Difference](http://codeforces.com/contest/1033/problem/B)
- simple math
- [1033A](http://codeforces.com/contest/1033/problem/A) King Escape
- simple logic
- 10/06
- leetcode weekly 105
- 920 Number of Music Playlists
- {2 hour+} hard DP
- 919 Complete Binary Tree Inserter
- imple recursion
- 918 Maximum Sum Circular Subarray
- prefix sum
- or find the complementary problem
- 917 Reverse Only Letters
- simple imple
- [(1059) Codeforces Round #514 (Div. 2)](http://codeforces.com/contest/1059)
- 1059A. Cashier
- simple imple
- 1059B. Forgery
- matching problem
- pypy speed up (but more memory)
- 1059C. Sequence Transformation
- constructive
- 1059D. Nature Reserve
- {DNF} binsearch
- 10/05
- Single Number II
- requires 2 extra bits to maintain the information of 1 bit
- (1, 0) -> (0, 1) -> (0, 0) group theory. induce the operation
- simple problems
- Two Sum
- hash
- Move Zeroes
- two pointers
- Plus One
- imple
- Intersection of Two Arrays II
- imple
- Best Time to Buy and Sell Stock II
- construct. property of increasing
- Rotate Array
- rotate by reversing
- Contains Dulicate
- hashing
- Single Number
- xor
- extensions: single Number II
- (lintcode) 1628. Driving problem
- graph+geometry+union-find set. good problem.
- (hackerrank) Lexicographic paths
- pattern find.
- 10/04
- (lintcode) 1624. Max Distance
- Trie. good problem. buggy, notice also need to recore the min
- (lintcode) 1625. Words Compression
- KMP. good problem. 1Pass!
- (lintcode) 1627. Word Segmentation
- imple
- (lintcode) 1629. Find the nearest store
- same as 1623. sort+binsearch
- (lintcode) 1630. Interesting String
- dfs+mem
- (lintcode) 1631. Interesting Subarray
- simple twopointers
- (lintcode) 1626. Salary Adjustment
- binsearch
- (lintcode) 1621. Cut Connection
- simple imple
- (lintcode) 1623. Minimal Distance In The Array
- sort binary search
- (lintcode) 1632. Count email groups
- trie
- 10/03
- 913. Cat and Mouse
- {buggy} minmax search.
- Range Sum Query 2D - Mutable
- 2d segmental tree.
- Zigzag Iterator
- imple
- Binary Search Tree Iterator
- recursion to interation. Use stack to keep track every returns
- Peeking Iterator
- simple design
- Moving Average from Data Stream
- simple design
- House Robber II
- DP. handle the cycle restriction by search(0, n-1) and (1, n)
- Minimum Path Sum
- basic DP
- Edit Distance
- 2d DP. note the replacement operator
- Maximum Vacation Days
- 2d DP
- 10/02
- 460. LFU Cache
- DoubleLinkedList inside DoubleLinkedList. One pass! :)
- Sentence Screen Fitting
- Greedy+DP.
- Word Break
- {buggy}. notice the boundaries
- Decode Ways
- dp.
- Evaluate Reverse Polish Notation
- stack. notice the definition of div
- Pacific Atlantic Water Flow
- BFS
- Next Greater Element I
- stack
- Merge Intervals
- {buggy}.
- 785. Is Graph Bipartite?
- dfs
- 261. Graph Valid Tree
- union-find set
- 10/01
- Diagonal Traverse
- imple. generate digonal list first
- Longest Palindromic Substring
- manacher's alg. notice `'^#'+'#'.join(s)+'#$'`
- Insert Interval
- {buggy} imple
- Range Module
- {DNF}. Ultra-hard.
- TLE with lazy-growing SegTree
- Require BST to achieve O(logN) when querying
- 09/30
- Sort Transformed Array
- case by case search
- Find K Pairs with Smallest Sums
- priority queue
- Find K-th Smallest Pair Distance
- heap: O(NlogK) = O(2NlogN) TLE
- sort and binary search the answer: O(nlogn)
- Shortest Distance from All Buildings
- BFS. reverse thinking
- Minimum Window Substring
- two pointers search
- Android Unlock Patterns
- dfs. notice the visited flag for the first element
- Word Search II
- notice words with only one char
- Strobogrammatic Number II
- dfs
- Word Squares
- dfs implementation
- 09/29
- Closest Binary Search Tree Value
- recursive
- Validate Binary Search Tree
- Simple recursive
- Course Schedule
- Simple topological sort
- 685. Redundant Connection II
- {DNF}. Hard.
- indeg with union find set
- Robot Room Cleaner
- backtrack
- dfs; keep track the direction, `move[(ind+k)%3]`
- 09/28
- Inorder Successor in BST
- {buggy}. Morris traversal.
- right children can be a backref-link or a normal link
- sol1. judge every where when stepping right
- sol2. handle differently when creating a backref-link
- 864. Shortest Path to Get All Keys
- BFS. states encoding
- 262. Trips and Users
- sqls. notice to use `u.banned` and `u2.banned` to join `user` table twice on different conditions
- 286. Walls and Gates
- BFS
- Evaluate Division
- build graph. notice the value of the reverse edge, same (s, t)
- Insert into a Cyclic Sorted List
- link. notice the boundary and equality
- Merge k Sorted Lists
- classic heap. Python3 RTE, use `id()` as secondary key
- Remove Duplicates from Sorted Array
- two pointer
- Move Zeroes
- simple twopointer
- First Unique Character in a String
- hash
- First Missing Positive
- hash using pos/neg. have to realize that the ans is in 1~n+1
- 09/27 (google list on leetcode)
- Shortest Palindrome
- palindrome. manacher's alg
- Max Consecutive Ones II (if we can flip at most one 0)
- imple.
- Max Consecutive Ones
- simple imple
- Intersection of Two Arrays
- simple hash
- Image Smoother
- simple imple
- Valid Parentheses
- simple imple, stack
- Valid Number
- regexp
- Valid Palindrome
- simple imple
- One Edit Distance
- simple imple: item zip(x, y) in is tuple
- Read N Characters Given Read4 II - Call multiple times
- {buggy} pay attention to situation when the buffer remains
- Read N Characters Given Read4
- buffer: [""] * N (assigned empty space)
- Add Bold Tag in String
- {buggy} KMP variation
- Plus One
- simple imple
- Spiral Matrix
- boundary imple
- 270. Closest Binary Search Tree Value
- simple imple
- 09/26
- Longest Substring with At Most K Distinct Characters
- hash
- License Key Formatting
- string, imple
- Longest Univalue Path
- recursive
- Next Closest Time
- imple
- K Empty Slots
- bucket
- Repeated String Match
- KMP mutation
- Robot Room Cleaner
- ideepcopy, imple
- Number of Islands
- pay attention
- Convert Binary Search Tree to Sorted Doubly Linked List
- when modifying morris traversal, check the type of right edge (normal/refer-back)
- Construct Binary Tree from Preorder and Inorder Traversal
- imple
- Binary Tree Vertical Order Traversal
- notice the tie-breaking condition
- 09/25
- **Lintcode Google ladder START**
- 507. Wiggle Sort II
- {DNF} O(N) search for median
- 825. Bus Station
- bfs
- 1544. Magic Square
- pure heuristic imple. waste of time
- 1555. Flower Problem
- union-find set
- 861. K Empty Slots
- BST
- {DNF} bucket by K
- 374. Spiral Matrix
- imple
- 386. Longest Substring with At Most K Distinct Characters
- two pointer scan
- 434. Number of Islands II
- Union-find set
- 513. Perfect Squares
- DP
- 532. Reverse Pairs
- mergesort.
- 706. Binary Watch
- imple
- 724. Minmum Partition
- knapsack
- 480. Binary Tree Paths
- dfs
- 937. How Many Problem Can I Accept
- math
- 1580. Transition String
- {buggy} topological sort.
- notice the duplicated edge
- 949. Fibonacci II
- Fast power
- 1577. Sum of leaf nodes
- {buggy} morris traversal
- 956. Data Segmentation
- string imple
- 1032. Letter Case Permutation
- dfs
- 1398. K Decimal Addition
- imple. notice prefix 0
- **Lintcode Google ladder END**
- 09/22
- 23. Merge k Sorted Lists
- heap
- 09/21
- 209. Minimum Size Subarray Sum
- slide window
- {buggy} 410. Split Array Largest Sum
- O(n^2logn) DP
- 566. Reshape the Matrix
- generator, imple
- 09/20
- ChapFB. Same Tree
- recursive
- ChapFB. Linked List Cycle
- Fast slow pointer
- ChapFB. Flatten Binary Tree to Linked List
- Morris traversal
- ChapFB. Intersection of Two Linked Lists
- check the requirement (O(N) vs onepass)
- ChapFB. Remove Nth Node From End of List
- two pointer
- ChapFB. Add Two Numbers
- Everytime write a while, write the update operation first
- ChapFB. Reverse Linked List
- iteratively and recursively
- ChapFB. Trapping Rain Water
- {DNF}. two pointer. keep a property
- ChapFB. Valid Parentheses
- stack
- ChapFB. Maximum Size Subarray Sum Equals k
- hash
- ChapFB. Minimum Size Subarray Sum
- two pointer
- ChapFB. Valid Number
- regex
- ChapFB. Valid Palindrome II
- imple
- ChapFB. Valid Palindrome
- two pointer
- ChapFB.
- {buggy} 3Sum
- use two pointer to eliminate the duplicates
- 09/19
- ChapterFB
- Move Zeroes
- imple
- Add Binary
- imple
- Intersection of Two Arrays II
- hash
- 568. Maximum Vacation Days
- DP. TLE with python3 but pass with python2
- 179. Largest Number
- `sorted(.., key=..)` `cmp` is not in python3
- `from functools import cmp_to_key`
- 733. Flood Fill
- check assumptions
- 695. Max Area of Island
- simple imple
- 48. Rotate Image
- odd even
- 207. Course Schedule
- topological sort
- 82. Remove Duplicates from Sorted List II
- read carefully
- 09/18
- {buggy} 372. Super Pow
- imple
- 318. Maximum Product of Word Lengths
- counter
- 09/17
- 28. Implement strStr()
- KMP
- ``` python
while cnd < len(p):
nxt[cnd] = nxt[pos] if p[pos] == p[cnd] else pos
while pos >= 0 and p[pos] != p[cnd]:
pos = nxt[pos]
pos += 1
cnd += 1
- rolling hash
- 307. Range Sum Query - Mutable
- segment tree
- binary indexed tree
- 303. Range Sum Query - Immutable
- segment tree
- 315. Count of Smaller Numbers After Self
- Good one.
- Mergesort
- Segment Tree
- sorted. Used the rank as index
- `ans += query(0, rank[i]); insert(rank[i], 1) `
- 09/15
- week contest 121
- 905. Sort Array By Parity
- simple imple
- 904. Fruit Into Baskets
- simple hash
- 907. Sum of Subarray Minimums
- tricky stack.
- {buggy} 906. Super Palindromes
- constructive.
- find the upper bound to try.
- 891. Sum of Subsequence Widths
- order not matter
- DP
- preprocess power.
- {buggy} 863. All Nodes Distance K in Binary Tree
- tree imple.
- 25. Reverse Nodes in k-Group
- list imple
- 835. Image Overlap
- imple. need to optimize the condition
- 09/14
- 146. LRU Cache
- design.
- 09/12
- {buggy} 32. Longest Valid Parentheses
- greedy, stack
- 543. Diameter of Binary Tree
- recursive
- 563. Binary Tree Tilt
- recursive
- 713. Subarray Product Less Than K
- two pointer, math.
- 209. Minimum Size Subarray Sum
- two pointer
- 452. Minimum Number of Arrows to Burst Balloons
- greedy
- 704. Binary Search
- binary search
- 337. House Robber III
- tree. check typo
- 328. Odd Even Linked List
- linked list
- 554. Brick Wall
- hash
- 287. Find the Duplicate Number
- inplace hash.
- 684. Redundant Connection
- Disjoint-set (union-find set)
- 477. Total Hamming Distance
- bucket.
- 869. Reordered Power of 2
- simple impl
- 241. Different Ways to Add Parentheses
- range DP. String
- 178. Rank Scores
- SQL. Note ambiguity
- {buggy} 845. Longest Mountain in Array
- simple imple. details.
- 191. Number of 1 Bits
- bit manipulation
- 09/09
- 894. All Possible Full Binary Trees
- recursive
- 384. Shuffle an Array
- simple impl
- 382. Linked List Random Node
- reservoir sample
- 09/06 (pandas day)
- 492. Construct the Rectangle
- simple math
- 733. Flood Fill
- simple dfs
- 387. First Unique Character in a String
- simple hash
- 447. Number of Boomerangs
- simple map
- 09/05
- 410. Split Array Largest Sum
- DP.
- O(N^2M). same code can pass with Python2 but not Python3 (WTH).
- O(NMlogN)). {buggy}
- 91. Decode Ways
- DP. onepass. boundaries
- 638. Shopping Offers
- DP. Multi-dim knapsack
- python is slow
- 689. Maximum Sum of 3 Non-Overlapping Subarrays
- 1D DP. one-pass
- 837. New 21 Game
- simple DP. optimize! using moving window and deque
- 304. Range Sum Query 2D - Immutable
- prefix sum.
- 09/04
- {buggy} 464. Can I Win
- min-max DP
- {buggy} 322. Coin Change
- step DP.
- initial
- 09/03
- 787. Cheapest Flights Within K Stops
- SPFA
- can pass with C++ but not Python (too slow)
- 576. Out of Boundary Paths
- simple graph DP. mem dfs
- {buggy} 801. Minimum Swaps To Make Sequences Increasing
- succeed on the 2nd try.
- {buggy} 673. Number of Longest Increasing Subsequence
- DP.
- 95. Unique Binary Search Trees II
- recursion. simulation.
- use memorization to reduce the space usage.
- 264. Ugly Number II
- hash heap.
- better way with math
- 375. Guess Number Higher or Lower II
- DP. good one but have less thumbs up than
- 09/02
- 847. Shortest Path Visiting All Nodes
- BFS+bit hashing. (path DP).
- 312. Burst Balloons
- Range DP
- 357. Count Numbers with Unique Digits
- Math
- 454. 4Sum II
- hash
- 383. Ransom Note
- imple
- 773. Sliding Puzzle
- dfs(with hash) (should use bfs). minimal path
- 09/01
- {buggy} 221. Maximal Square
- DP.
- {DNF} 523. Continuous Subarray Sum
- better property. boundary.
- {DNF} 898. Bitwise ORs of Subarrays
- BF. but with careful complexity analysis
- 51. N-Queens
- 52. N-Queens II
- bit manipulation
- 503. Next Greater Element II
- padding
- {buggy} 765. Couples Holding Hands
- hash
- {buggy} 216. Combination Sum III
- boundary
- 217. Contains Duplicate
- meaningless
- {buggy} 819. Most Common Word
- details on assumption (input)
- {buggy} 769. Max Chunks To Make Sorted
- imple
- 08/31
- {buggy} 538. Convert BST to Greater Tree
- None
- 206. Reverse Linked List
- recursive way
- 717. 1-bit and 2-bit Characters
- imple
- 122. Best Time to Buy and Sell Stock II
- imple
- (7) {DNF} 421. Maximum XOR of Two Numbers in an Array
- Trie
- 08/30
- 648. Replace Words
- TrieTree
- 895. Maximum Frequency Stack
- imple
- 858. Mirror Reflection
- imple
- 169. Majority Element
- IQ
- 13. Roman to Integer
- imple
- 676. Implement Magic Dictionary
- imple
- {buggy} 860. Lemonade Change
- imple
- 171. Excel Sheet Column Number
- imple
- {DNF} 128. Longest Consecutive Sequence
- hash
- 547. Friend Circles
- DFS.
- 781. Rabbits in Forest
- hash
- 565. Array Nesting
- imple
- 653. Two Sum IV - Input is a BST
- generator with `yield from`
- range search
- 653. Two Sum IV - Input is a BST
- detail
- {buggy} 677. Map Sum Pairs
- imple
- {DNF} 371. Sum of Two Integers
- bit
- {DNF} 667. Beautiful Arrangement II
- IQ
- 08/29
- 696. Count Binary Substrings
- imple. detail
- 817. Linked List Components
- simple imple
- {DNF} 448. Find All Numbers Disappeared in an Array
- IQ
- 495. Teemo Attacking
- simple imple
- 389. Find the Difference
- IQ
- 690. Employee Importance
- simple hash
- 520. Detect Capital
- simple. imple
- 462. Minimum Moves to Equal Array Elements II
- IQ
- {buggy} 283. Move Zeroes
- two pointer
- 789. Escape The Ghosts
- simple imple
- 748. Shortest Completing Word
- hash. imple
- 451. Sort Characters By Frequency
- simple imple
- 508. Most Frequent Subtree Sum
- search
- {DNF} 260. Single Number III
- IQ
- {30+}{buggy} 889. Construct Binary Tree from Preorder and Postorder Traversal
- Details
- {10+}{buggy} 856. Score of Parentheses
- Details
- {5} 429. N-ary Tree Level Order Traversal
- BFS
- 485. Max Consecutive Ones
- simple imple
- 812. Largest Triangle Area
- brutal force.
- 784. Letter Case Permutation
- DFS
- 526. Beautiful Arrangement
- DFS
- 695. Max Area of Island
- 200. Number of Islands
- dfs. flood fill
- 08/28
- 647. {15} Palindromic Substrings
- DP
- [Manacher’s Algorithm](https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/)
```
if i < right: # in affected area
f[i] = min(f[2*center-i], right-i)
else:
f[i] = 1 # out of range
while s[i+f[i]] == s[i-f[i]]: # append different front and end to prevent overflow
f[i] += 1
if i+f[i] > right: # update the boundary
right = i+f[i]
center = i
```
- 446. {1/2DNF} Arithmetic Slices II - Subsequence
- hash+DP.
- 413. {5} Arithmetic Slices
- imple
- 739. {5} Daily Temperatures
- stack.
- rabin-karp
- 08/27
- 632. {DNF} Smallest Range
- heap. hard
- 438. Find All Anagrams in a String
- hashing.
- 1. Two Sum
- hash.
- 202. Happy Number
- hash.
- 242. Valid Anagram
- hash
- 347. Top K Frequent Elements
- hash heap
- 349. Intersection of Two Arrays
- set, intersection
- 350. Intersection of Two Arrays II
- hash
- 08/26
- 888. Fair Candy Swap
- math.
- 693. Binary Number with Alternating Bits
- details.
- 540. {20} Single Element in a Sorted Array
- binary search. detail
- 762. Prime Number of Set Bits in Binary Representation
- bincount
- 515. Find Largest Value in Each Tree Row
- bfs
- 521. Longest Uncommon Subsequence I
- imple
- 292. Nim Game
- logic
- 877. Stone Game
- tricky logic
- 553. Optimal Division
- details
- 824. Goat Latin
- imple
- 08/25
- 463. Island Perimeter
- detail. transfer summation to subtraction.
- 669. Trim a Binary Search Tree
- use the returned result to update current node
- 412. Fizz Buzzj
- imple.
- 442. Find All Duplicates in an Array
- use the condition provided by the problem.
- 566. Reshape the Matrix
- imple.
- 700. Search in a Binary Search Tree
- imple.
- 841. Keys and Rooms
- Graph dfs.
- 496. {DNF} Next Greater Element I
- stack and hash
- 406. {DNF} Queue Reconstruction by Height
- insertion
- 513. Find Bottom Left Tree Value
- tree bfs.
Alg doc (before Aug)
===
- 1->10 (simplest -> hardest)
- Others
- Greedy
- (3) {10} 861. Score After Flipping Matrix
- Greedy
- (3) {10} 763. Partition Labels
- Note the details.
- Implementation
- 728. Self Dividing Numbers
- one-line python
- Data Structure
- Tree
- 669. Trim a Binary Search Tree
- use the returned value to update current node
- 872. Leaf-Similar Trees
- Note reference equal vs value equal
- 814. Binary Tree Pruning
- careful about the boundary
- (4) 654. Maximum Binary Tree
- tricky. Note: change of node doesn't change references that point to it.
- simple ones:
- 104, 110, 109, 257, 783, 530
- 404. Sum of Left Leaves
- use default arguments to separate root from non-root
- 226. Invert Binary Tree
- Note: the link list will change after changing
- 100. Same Tree
- base case None
- 111. Minimum Depth of Binary Tree
- base return inf to avoid min
- 124. Binary Tree Maximum Path Sum
- return max sum from current note to leaf.
- 101. Symmetric Tree
- Note: __eq__ of treenode is undefined
- 236. Lowest Common Ancestor of a Binary Tree
- Clarify the type of input.
- Linklist
- 83/82/19. Remove Duplicates from Sorted List
- Linklist
- 707. Design Linked List
- Linklist Implementation
- 876. Middle of the Linked List
- Classic two pointer.
- 203. Remove Linked List Elements
- Note: Duplicate consecutive value.
- Queue
- 641. Design Circular Deque
- double linked list
- 622. Design Circular Queue
- fixed length data-structure: use fixed length list with looping indices
- Stack
- 150. Evaluate Reverse Polish Notation
- stack. note: division trap
- 155. Min Stack
- stack. maintain another stack
- 225. Implement Stack using Queues
- looped queue.
- 232. Implement Queue using Stacks
- double stacks.
- Leetcode (DP special from July/31) (38)
- (2) {10} 467. Unique Substrings in Wraparound String
- Simple DP.
- (3) {15} 790. Domino and Tromino Tiling
- step DP.
- (4) {20} 698. Partition to K Equal Sum Subsets
- mem search. Bit-status
- (4) {DNF} 808. Soup Servings
- mem search. Note: estimate the **actual** boundary (p approximates 1.00)
- (4) {10} 368. Largest Divisible Subset
- simple DP with sol output.
-
- (3) {14} 376. Wiggle
- Greedy. Careful about the beginning.
- (5) {20} 213. House Robber II
- Step DP. Two cases.
- (3) {10} 279. Perfect Squares
- Knapsack DP.
- (3) {10} 416. Partition Equal Subset Sum
- knapsack DP.
- (3) {10} 474. Ones and Zeroes
- 2d knapsack DP.
- (2) {4} 300. Longest Increasing Subsequence
- LIS. classic DP
- (2) {10} 838. Push Dominoes
- Simple sim.
- (3) {15} 764. Largest Plus Sign
- Grid DP. Prefix sum.
- (3) 688. Knight Probability in Chessboard
- pure simulation.
- (5) {20+} 873. Length of Longest Fibonacci Subsequence
- DP + binary search. Good one.
- (3) {20} 813. Largest Sum of Averages
- Range DP. Note: safe solution first. Don't have to be the optimal at first.
- (3) {10} 718. Maximum Length of Repeated Subarray
- LCS variation.
- (2) {10} 64. Minimum Path Sum
- Simple Grid DP.
- (4) {15} 309. Best Time to Buy and Sell Stock with Cooldown
- Stock DP. Note: be clear about your definition of f[i]
- (3) {5} 96. Unique Binary Search Trees
- Pattern finding.
- (3) {6} 377. Combination Sum IV
- search with memorization.
- (3) {13} 516. Longest Palindromic Subsequence
- range DP. Note: special case handling.
- (3) {5} 740. Delete and Earn
- 1D DP.
- (4) {15} 494. Target Sum
- memorization search. Note: if answer is 0, check initialization or boundary (base case).
- (4) {10} 392. Is Subsequence
- LCS problem. dimension compression (reference in C++).
- (6) {20} 486. Predict the Winner
- minmax DP.
- (2) {7} 650. 2 Keys Keyboard
- Split DP.
- (3) {10} 343. Integer Break
- Split DP. Careful about what `f[n]` means (usually comes with assumption(the splitted score))
- (5) {30} 714. Best Time to Buy and Sell Stock with Transaction Fee
- Ascending property. O(N^2) to O(N). Careful about the boundary.
- (4) {10} 646. Maximum Length of Pair Chain
- LIS problem. TLE with Python but not C++.
- (5) {30+} 712. Minimum ASCII Delete Sum for Two Strings
- grid DP. Boundary should consider the
- (2) 746. Min Cost Climbing Stairs
- simple stair DP.
- (2) 198. House Robber
- simple DP.
- (1) 121. Best Time to Buy and Sell Stock
- stock DP.
- (1) 70. Climbing Stairs
- step DP.
- (1) 53. Maximum Subarray
- ascending prop
- (2) 303. Range Sum Query-Immutable
- Prefix sum.
- (2) 383. Counting Bits
- pattern finding.
- (1) 413. Arithmetic slice
- ascending DP.
- (3) 647. Palindromic Substrings
- range DP.
- (1) 62. Unique Paths
- simple #solution counting.
- History
- Leetcode
- (3) 152. Constructive. Swap min, max strategy.
- (3) 238. Constructive. Bidirectional prefix.
- (3) 42. DP. Bidirectional scan.
- cf_edu_r44(985)
- (1). A, B
- (2). C. Greedy, constructive.
- (3). D. Binary search
- (5). E. Interval DP. Interval set
- (6). F. Vector Hash, use power to replace shift (O(N) to O(1))
- cf_483_div2
- (1). A, B. Simple simulation
- (4). C. Number theory.
- (4). D. Interval DP.
- cf_482_div2
- (1). B. Logit.
- (3). Easy graph theory.
- (5). Binary Tire. Finding the maximum XOR of $x_i$ with v. Divisor group.
- cf_480_div2
- (2) B. Simulation. Logit. Symmetric construction.
- (3) C. Greedy. Notice the greedy design (do not exaggerate the assumption).
- (5) D. Simplify the numbers first to avoid redundant computation.
- LeetCode
- (2) [820. Short Encoding of Words](https://leetcode.com/problems/short-encoding-of-words/description/)
- simple string processing.
- (2) [821. Shortest Distance to a Character](https://leetcode.com/problems/shortest-distance-to-a-character/description/)
- simple. two ways scan.
- (3) [822. Card Flipping Game](https://leetcode.com/problems/card-flipping-game/description/)
- logic+hash
- (5) [823.Binary Trees With Factors](https://leetcode.com/problems/binary-trees-with-factors/description/)
- Simple DP. Use `unordered_map` (hash) to make the query to `O(1)`.
- (2) [114. Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list)
- Recursive. Pay attention to the fakeroot and self loop.
- (2) [120. Triangle](https://leetcode.com/problems/triangle)
- DP. Reusing the space.
- (2) [129. Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers)
- Simulation. Pay attention to the boundary.
- (5) [131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning)
- DP+DFS. Can summarize the answer online without DFS (offline) by accumulate the answer list.
- (4) [132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii)
- DP.
- (6) [134. Gas Station](https://leetcode.com/problems/gas-station)
- Increasing seq. Details on the boundary.
- (4) [135. Candy](https://leetcode.com/problems/candy)
- Logic. Simplify the restriction to larger than left and right and maintain it by two scanning.
- [One pass method.](https://leetcode.com/problems/candy/discuss/42770/One-pass-constant-space-Java-solution) Consider the property of being descending.
- (7) [137. Single Number II](https://leetcode.com/problems/single-number-ii)
- Logic. On/off status of each bit.
- Create a group (mathematical) "0->1->2->3/0" to simplify the code. [link](https://piazza.com/class/jbzpcp2r9tg7b3?cid=183). Xor is actual a group operation in binary case.
- (5) [138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer)
- List Logic. Use association to reduce the memory usage.
- pile up the original one with the new one.
- (3) [139. Word Break](https://leetcode.com/problems/word-break)
- Simple DP.
- (4) [140. Word Break II](https://leetcode.com/problems/word-break-ii)
- Simple DP. Python's speed issue.
- (5) [115. Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences)
- DP. O(N^3). Should be O(N^2).
- (3) [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle)
- Link-list Logic.
- (6) [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii)
- Link-list logic. Hard.
- (4)[143. Reorder List](https://leetcode.com/problems/reorder-list)
- Link-list impl.
- (6) [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal)
- [Morris traversal](https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html). Threaded binary tree. Use right child to refer back and use the "refer back " property to judge whether we traversed this node.
- use the empty right children (refer parent) and change it back later (judge whether there is a loop)
- (1) [147. Insertion Sort List](https://leetcode.com/problems/insertion-sort-list)
- (2) [148. Sort List](https://leetcode.com/problems/sort-list)