LeetCode Problems & Solutions.
# | Title | Solution | Topic | Basic Idea |
---|---|---|---|---|
1 | Two Sum | Python | Array , Hash Table |
HashTable: While scanning through the array, wait for the target - x using hash map |
15 | 3Sum | Python | Two Pointers , Sorting |
4 Cases exist: [0,0,0], [0,p,-p], [p1,p2,-(p1+p2)], [n1, n2, -(n1+n2)] |
22 | Generate Parentheses | Python | DP , Backtracking , Stack |
Stack: stack=[("(", l, r)] |
45 | Jump Game II | Python | DP , Greedy |
DP: O(n^2), Greedy: (TBD) |
46 | Permutations | Python | Backtracking |
Backtrack: Add nums[i] -> Go next -> Pop nums[i] with visited flag |
55 | Jump Game | Python | DP , Greedy |
Greedy: (Forward) if cur position > max position then False (Backward) if last position can reach the first index then True |
62 | Unique Paths | Python | Combinatorics , DP |
Combinatorics: (m+n-2)C(m-1), DP: dp[i][j]=dp[i-1][j]+dp[i][j-1] |
70 | Climbing Stairs | Python | DP , Math |
DP: dp[i]=dp[i-1]+dp[i-2] where dp[0]=1 |
71 | Simplify Path | Python | String , Stack |
Stack: .. (pop), . or empty (ignore), else (push) |
77 | Combinations | Python | Backtracking |
Backtrack: Add i -> Go next -> Backtrack (=pop i) |
78 | Subsets | Python | Backtracking , Bit Manipulation |
Cascading: Append nums[i] (doubling the size of previous one) Backtrack: Add nums[i] -> Go next -> Backtrack (=pop nums[i]) |
90 | Subsets II | Python | Backtracking , Bit Manipulation |
Backtrack: Same idea as #78 + set.add(tuple(sorted(list))) to remove duplicates |
101 | Symmetric Tree | Python | DFS , BFS , Stack |
DFS(Recursive): dfs(l.l, r.r) and dfs(l.r, r.l) Stack(Iterative): Basically, mirror idea is SAME & return False when one is None or vals are different |
112 | Path Sum | Python | BinarySearch , DFS , BFS |
BFS: (root, acc_sum) DFS: (targetSum-root.val) for left and right, recursively |
113 | Path Sum II | Python | DFS , BFS , Backtracking |
BFS: (root, [root.val]) |
172 | Factorial Trailing Zeroes | Python | Math |
O(N): dp[i]=i//5 + dp[i//5] if i%5==0 O(logN): Add # of 5s and then # of 25s ... until it reaches N |
200 | Number of Islands | Python | DFS , BFS , UnionFind |
DFS: dfs(x+dx, y+dy) BFS: queue=[(x,y)] |
221 | Maximal Square | Python | DP |
DP: DP[i][j]=min(DP[i][j-1], DP[i-1][j], DP[i-1][j-1])+1 |
231 | Power of Two | Python | Bit Manipulation |
BitManipulation: (2^n) and (2^n)-1 are always complementary |
287 | Find the Duplicate Number | Python | Two Pointers , Binary Search , Bit Manipulation |
TwoPointers: |
322 | Coin Change | Python | DP , BFS |
DP: dp[i]=min(dp[i-coins[0]], dp[i-coins[1]], dp[i-coins[2]], ... )+1 |
326 | Power of Three | Python | Math , NumberTheory |
Math: math.log(n, 3) , NumberTheory: Check max pow(3)%n |
342 | Power of Four | Python | Bit Manipulation , Math |
Math: math.log(n, 4) |
437 | Path Sum III | Python | DFS , BFS |
(TBD) |
518 | Coin Change 2 | Python | DP |
DP: dp[i]+=dp[i-coin] (Key idea: For-loop-coin-first-then-amount) |
1051 | Height Checker | Python | Sort , CountingSort |
Sort: 1-Liner using zip & sort |
1200 | Minimum Absolute Difference | Python | Sorting |
Sort and find the min with zip (arr, arr[1:]) |
1268 | Search Suggestions System | Python | Trie , BinarySearch |
BinarySearch: sort and bisect_left Trie: (TBD) |
1306 | Jump Game III | Python | DFS , BFS |
BFS: q=[index] and A[index]=-1 DFS: return A[index]==0 or f(index+A[index]) or f(index-A[index]) |
1512 | Number of Good Pairs | Python | HashTable , Math , Counting |
Math: set and count (but it requires modification of the given array), HashTable: Frequency Table is all you need |
2000 | Reverse Prefix of Word | Python | TwoPointers , String |
String: index and [::-1] |
Categories: Dynamic Programming (DP), BFS, DFS, Math, Stack, Queue, Hash Table, Back Tracking, Graph
- Backtrack: Find all the possible cases for the given situation
- DP:
- BFS:
- DFS:
- index vs find
- set vs list