Skip to content

Latest commit

 

History

History
266 lines (228 loc) · 22.7 KB

README.md

File metadata and controls

266 lines (228 loc) · 22.7 KB

Algorithm

My personal leetcode answers
This is a continually updated, open source project.

🎉🎉🎉 Finished 100 questions on 2018-05-28
🎉🎉🎉 Finished 150 questions on 2018-06-29

References

☝️Hey!!!, its clickable. references are moved💦

Leetcode

Math

Problem Solution Time Difficulty Tag Note
202.happy-number cpp, python O(N) Easy
836.rectangle-overlap cpp O(1) Easy

Bit Manipulation

Problem Solution Time Difficulty Tag Note
136.single-number cpp O(N) Easy

Array and String

Problem Solution Time Difficulty Tag Note
53.maximum-subarray python O(N) Easy
54.spiral-matrix cpp O(N) Medium
66.plus-one cpp O(N) Easy
118.pascals-triangle cpp O(N^2) Easy
240.search-a-2d-matrix-ii cpp, python O(N + M) Medium
350.intersection-of-two-arrays-ii python O(N * logN) Easy
485.max-consecutive-ones cpp O(N) Easy
498.diagonal-traverse cpp O(M * N) Medium
560.subarray-sum-equals-k python O(N) Medium
561.array-partition-i cpp O(N * logN) Easy
724.find-pivot-index cpp O(N) Easy
747.largest-number-at-least-twice-of-others cpp O(N) Easy
796.rotate-string cpp, python O(N^2) Easy string TODO: Rabin-Karp Algorithm, KMP algorithm
859.buddy-strings cpp O(N) Easy string

Two Pointers

Problem Solution Time Space Difficulty Tag Note
003.longest-substring-without-repeating-characters cpp, python O(N) O(N) Medium
026.remove-duplicates-from-sorted-array cpp, python O(N) O(1) Easy
027.remove-element cpp, python O(N) O(1) Easy
028.implement-strstr cpp, python O(N^2) O(1) Easy TODO: string, KMP, rolling hash?
076.minimum-window-substring cpp, python O(N) O(N) Hard
088.merge-sorted-array cpp, python O(N + M) O(1) Easy
125.valid-palindrome cpp, python O(N) O(1) Easy
141.linked-list-cycle cpp, python O(N) O(1) Easy
159.longest-substring-with-at-most-two-distinct-characters cpp, python O(N) O(N) HARD
167.two-sum-ii-input-array-is-sorted cpp, python O(N) O(1) Easy
209.minimum-size-subarray-sum cpp, python O(N) O(1) Medium
234.palindrome-linked-list cpp, python O(N) O(1) Easy maybe harder
283.move-zeroes cpp, python O(N) O(1) Easy
340.longest-substring-with-at-most-k-distinct-characters cpp, python O(N) O(N) HARD
344.reverse-string cpp, python O(N) O(1) Easy
345.reverse-vowels-of-a-string cpp, python O(N) O(1) Easy
349.intersection-of-two-arrays cpp, python O(K * logK), k = max(M, N) O(1) Easy hash, binary-search
350.intersection-of-two-arrays-ii cpp, python O(K * logK), k = max(M, N) O(1) Easy hash, binary-search
532.k-diff-pairs-in-an-array cpp, python O(N * logN) O(1) Easy Hash
844.backspace-string-compare cpp, python O(N) O(1) Easy stack

Two Pointers(legacy)

Problem Solution Time Difficulty Tag Note
15.3sum cpp, python O(N^2) Medium
16.3sum-closest cpp, python O(N^2) Medium
18.4sum cpp, python O(N^3) Medium
19.remove-nth-node-from-end-of-list cpp, python O(N) Medium
75.sort-colors cpp python O(N) Medium counting-sort
142.linked-list-cycle-ii python O(N) Medium linked-list
160.intersection-of-two-linked-lists python O(N + M) Easy linked-list

Linked List

Problem Solution Time Difficulty Tag Note
21.merge-two-sorted-lists cpp, python O(N) Easy
25.reverse-nodes-in-k-group python O(N) Hard
61.rotate-list python O(N) Medium
86.partition-list python O(N) Medium
92.reverse-linked-list-ii python O(N) Medium
138.copy-list-with-random-pointer python O(N) Medium
143.reorder-list python O(N) Medium
148.sort-list python O(N * logN) Medium
203.remove-linked-list-elements python O(N) Easy
206.reverse-linked-list python O(N) Easy
237.delete-node-in-a-linked-list python O(1) Easy
328.odd-even-linked-list python O(N) Medium

Binary Search

Problem Solution Time Difficulty Tag Note
33.search-in-rotated-sorted-array cpp, python O(logN) Medium
34.find-first-and-last-position-of-element-in-sorted-array cpp Medium
74.search-a-2d-matrix cpp, python O(logN) Medium N = row * column
81.search-in-rotated-sorted-array-ii cpp, python O(logN) ~ O(N) Medium
153.find-minimum-in-rotated-sorted-array cpp, python O(logN) Medium
154.find-minimum-in-rotated-sorted-array-ii cpp, python O(logN) ~ O(N) Hard
162.find-peak-element cpp O(logN) Meidum
302.smallest-rectangle-enclosing-black-pixels cpp O(M * N) / O(N * LogN) Hard
Problem Solution Time Space Difficulty Tag Note
069.sqrtx cpp, python O(logN) O(1) Easy
278.first-bad-version cpp, python O(logN) O(1) Easy
704.binary-search cpp, python O(logN) O(1) Easy
852.peak-index-in-a-mountain-array cpp, python O(logN) O(1) Easy Golden-section search

Divide and Conquer

Problem Solution Time Difficulty Tag Note
4.median-of-two-sorted-arrays cpp, python O(log(M + N)) Hard
98.validate-binary-search-tree cpp, python O(N) Medium TODO: inorder-traversal
104.maximum-depth-of-binary-tree cpp, python O(N) Easy
110.balanced-binary-tree cpp, python O(N) Easy
236.lowest-common-ancestor-of-a-binary-tree cpp, python O(N) Medium

Tree Traversal

Problem Solution Time Difficulty Tag Note
94.binary-tree-inorder-traversal cpp O(N) Medium
102.binary-tree-level-order-traversal cpp O(N) Medium
107.binary-tree-level-order-traversal-ii cpp O(N) Easy
144.binary-tree-preorder-traversal cpp O(N) Medium

Graph Traversal

Problem Solution Time Difficulty Tag Note
127.word-ladder python O(N * L^2) Medium BFS
200.number-of-islands python O(M x N) Medium BFS/DFS union-find
207.course-schedule cpp O(V + E) Medium
210.course-schedule-ii cpp O(V + E) Medium topological-sort
444.sequence-reconstruction cpp, python O(V+E) Medium topological-sort

Backtracking

Problem Solution Time Difficulty Tag Note
39.combination-sum python ??? Medium DFS
40.combination-sum-ii python ??? Medium DFS
46.permutations python ??? Medium DFS
47.permutations-ii python ??? Medium DFS
51.n-queens python ??? Hard DFS
52.n-queens-ii python ??? Hard DFS
78.subsets cpp, python O(N * 2^N) Medium DFS bit-manipulation / iterative
90.subsets-ii cpp, python O(N * 2^N) Medium DFS bit-manipulation
126.word-ladder-ii python O((V+E) * L^2) Hard BFS+DFS
131.palindrome-partitioning python ??? Medium DFS
Problem Solution Time Space Difficulty Tag Note
079.word-search cpp, python O(M * N * L * L) O(M * N) Medium DFS L = length of words

Hash Table

Problem Solution Time Difficulty Tag Note
1.two-sum cpp, python O(N) Easy
36.valid-sudoku cpp O(N ^ 2) Medium array-indexes
49.group-anagrams cpp O(N * k * Logk) Medium
170.two-sum-iii-data-structure-design cpp, python O(N) Easy
202.happy-number cpp, python O(N) Easy
205.isomorphic-strings cpp, python O(N) Easy
217.contains-duplicate cpp O(N) Easy
219.contains-duplicate-ii cpp O(N) Easy
249.group-shifted-strings cpp O(N * K) Medium
288.unique-word-abbreviation cpp - Medium
347.top-k-frequent-elements cpp O(N * LogN) Medium TODO: quick-sort, bucket-sort
349.intersection-of-two-arrays cpp O(M + N) Easy
350.intersection-of-two-arrays-ii cpp O(M * N) Easy
359.logger-rate-limiter cpp O(1) Easy amortized
380.insert-delete-getrandom-o1 cpp O(1) Medium
454.4sum-ii cpp O(N ^ 2) Medium
599.minimum-index-sum-of-two-lists cpp O(M + N) Easy
652.find-duplicate-subtrees cpp O(N) Medium
771.jewels-and-stones cpp O(M + N) Easy

heap

Problem Solution Time Space Difficulty Tag Note
23.merge-k-sorted-lists cpp O(N * LogK) - Hard TODO: merge-sort, bottom-up
378.kth-smallest-element-in-a-sorted-matrix cpp, python O((K + M) * LogM) O(M) Medium TODO: binary-search, O(N) solution

Dynamic Programming

Problem Solution Time Difficulty Tag Note
62.unique-paths python O(M * N) Medium Coordinates
63.unique-paths-ii python O(M * N) Medium Coordinates
64.minimum-path-sum python O(M * N) Medium Coordinates
70.climbing-stairs cpp, python O(N) Easy Coordinates
91.decode-ways cpp O(N) Medium conditional-climbing-stairs
120.triangle cpp, python O(N^2) Medium Coordinates
300.longest-increasing-subsequence cpp, python O(N^2) Medium follow-up is tricky
354.russian-doll-envelopes cpp, python O(N^2) Hard TODO: Python Version Time Limit Exceeded
368.largest-divisible-subset cpp O(N^2) Medium
403.frog-jump cpp O(N^2) Hard

Greedy

Problem Solution Time Difficulty Tag Note
45.jump-game-ii cpp, python O(N) Hard
55.jump-game cpp, python O(N) Medium dynamic-programming

Union Find

Problem Solution Time Space Difficulty Tag Note
128.longest-consecutive-sequence cpp O(N) - Hard
261.graph-valid-tree cpp, python O(N) O(N) Medium BFS/DFS
305.number-of-islands-ii cpp, python O(N) O(M * N) Hard N = len(positions)
721.accounts-merge cpp, python O(M * N) O(M * N) Medium

Trie

Problem Solution Time Space Difficulty Tag Note
208.implement-trie-prefix-tree cpp, python O(L) <= (N * L) Medium - L = len(word), N = number of words
211.add-and-search-word-data-structure-design cpp, python add = O(L), find >= O(L) <= O(N * L) Medium DFS L = len(word), N = number of words
212.word-search-ii cpp, python O(M * N * L * L) MAX(O(M * N), O(K * L)) HARD DFS K = number of words, L = avg length of words

Other

Problem Solution Time Space Difficulty Tag Note
215.kth-largest-element-in-an-array cpp, python O(N) O(1) Medium quick-select best = O(N), worst = O(N^2)

Lintcode

Problem Solution Time Space Difficulty Tag Note
465.kth-smallest-sum-in-two-sorted-arrays cpp, python O((K + N) * LogN) O(N) Hard heap N = B.size()
543.kth-largest-in-n-arrays cpp, python O(M * N * LogK) O(K) Easy heap
589.connecting-graph cpp, python O(1) O(N) Medium union-find
590.connecting-graph-ii cpp, python O(1) O(N) Medium union-find
591.connecting-graph-iii cpp, python O(1) O(N) Medium union-find
629.minimum-spanning-tree cpp, python O(N * logN) O(N) Hard union-find, Kruskal Prim