Skip to content
No description or website provided.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
data-structures data structure Apr 5, 2019
imgs
other other Apr 22, 2019
1.two-sum.rb
10.regular-expression-matching.rb 10 Mar 31, 2019
1005.maximize-sum-of-array-after-k-negations.rb 1005 Apr 4, 2019
101.symmetric-tree.rb 101 Apr 12, 2019
1012.complement-of-base-10-integer.rb 1012 Mar 31, 2019
1013.pairs-of-songs-with-total-durations-divisible-by-60.rb
1014.capacity-to-ship-packages-within-d-days.rb 1014 Mar 31, 2019
102.binary-tree-level-order-traversal.rb 102 Mar 31, 2019
1021.remove-outermost-parentheses.rb 1021 Apr 22, 2019
1022.sum-of-root-to-leaf-binary-numbers.rb 1022 Apr 22, 2019
1023.camelcase-matching.rb
1024.video-stitching.rb
1025.divisor-game.rb
1026.maximum-difference-between-node-and-ancestor.rb
1027.longest-arithmetic-sequence.rb
1028.recover-a-tree-from-preorder-traversal.rb 1028 Apr 22, 2019
1029.two-city-scheduling.rb 1029 Apr 22, 2019
103.binary-tree-zigzag-level-order-traversal.rb
1030.matrix-cells-in-distance-order.rb 1030 Apr 22, 2019
1031.maximum-sum-of-two-non-overlapping-subarrays.rb 1031 Apr 22, 2019
1032.stream-of-characters.rb 1032 Apr 22, 2019
1033.moving-stones-until-consecutive.rb 1033 May 7, 2019
1034.coloring-a-border.rb 1034 May 7, 2019
1035.uncrossed-lines.rb 1035 May 7, 2019
1037.valid-boomerang.rb 1037 May 7, 2019
1038.binary-search-tree-to-greater-sum-tree.rb 1038 May 7, 2019
1039.minimum-score-triangulation-of-polygon.rb
104.maximum-depth-of-binary-tree.rb 104 Mar 31, 2019
1041.robot-bounded-in-circle.rb 1041 May 12, 2019
1042.flower-planting-with-no-adjacent.rb 1042 May 12, 2019
1043.partition-array-for-maximum-sum.rb 1043 May 12, 2019
105.construct-binary-tree-from-preorder-and-inorder-traversal.rb 105 Mar 31, 2019
106.construct-binary-tree-from-inorder-and-postorder-traversal.rb 106 Mar 31, 2019
108.convert-sorted-array-to-binary-search-tree.rb 108 Mar 31, 2019
11.container-with-most-water.rb
110.balanced-binary-tree.rb
111.minimum-depth-of-binary-tree.rb 111 Mar 31, 2019
112.path-sum.rb 112 Mar 31, 2019
113.path-sum-ii.rb 113 Mar 31, 2019
116.populating-next-right-pointers-in-each-node.rb 116 May 12, 2019
118.pascals-triangle.rb
119.pascals-triangle-ii.rb 119 Apr 23, 2019
121.best-time-to-buy-and-sell-stock.rb
122.best-time-to-buy-and-sell-stock-ii.rb 122 Apr 22, 2019
123.best-time-to-buy-and-sell-stock-iii.rb
124.binary-tree-maximum-path-sum.rb 124 May 12, 2019
125.valid-palindrome.rb 125 May 12, 2019
126.word-ladder-ii.rb 126 Apr 22, 2019
127.word-ladder.rb 127 Apr 22, 2019
128.longest-consecutive-sequence.rb 128 Mar 31, 2019
13.roman-to-integer.rb 13 Mar 31, 2019
130.surrounded-regions.rb 130 Mar 31, 2019
131.palindrome-partitioning.rb 131 May 12, 2019
134.gas-station.rb 134 May 12, 2019
136.single-number.rb 136 Mar 31, 2019
138.copy-list-with-random-pointer.rb
139.word-break.rb 139 Apr 22, 2019
14.longest-common-prefix.rb 14 May 8, 2019
140.word-break-ii.rb 140 May 12, 2019
141.linked-list-cycle.rb
144.binary-tree-preorder-traversal.rb
146.lru-cache.rb 146 Apr 11, 2019
148.sort-list.rb
149.max-points-on-a-line.rb
15.3sum.rb
150.evaluate-reverse-polish-notation.rb 150 May 13, 2019
151.reverse-words-in-a-string.rb
152.maximum-product-subarray.rb
155.min-stack.rb
157.read-n-characters-given-read4.rb 157 Apr 10, 2019
16.3sum-closest.rb 16 Apr 2, 2019
160.intersection-of-two-linked-lists.rb 160 May 13, 2019
162.find-peak-element.rb
163.missing-ranges.rb 163 May 13, 2019
166.fraction-to-recurring-decimal.rb
167.two-sum-ii-input-array-is-sorted.rb 167 Apr 23, 2019
169.majority-element.rb 169 Mar 31, 2019
17.letter-combinations-of-a-phone-number.rb
171.excel-sheet-column-number.rb
172.factorial-trailing-zeroes.rb 172 May 14, 2019
186.reverse-words-in-a-string-ii.rb
189.rotate-array.rb 189 Apr 11, 2019
19.remove-nth-node-from-end-of-list.rb 19 May 8, 2019
191.number-of-1-bits.rb
198.house-robber.rb 198 Apr 5, 2019
199.binary-tree-right-side-view.rb
2.add-two-numbers.rb 2 Apr 13, 2019
20.valid-parentheses.rb
200.number-of-islands.rb 200 Mar 31, 2019
202.happy-number.rb
203.remove-linked-list-elements.rb 203 Apr 22, 2019
204.count-primes.rb 204 Apr 22, 2019
206.reverse-linked-list.rb 206 Apr 22, 2019
207.course-schedule.rb 207 Apr 8, 2019
208.implement-trie-prefix-tree.rb
209.minimum-size-subarray-sum.rb
21.merge-two-sorted-lists.rb 21 Apr 13, 2019
210.course-schedule-ii.rb 210 Apr 8, 2019
212.word-search-ii.rb 212 Apr 22, 2019
213.house-robber-ii.rb
215.kth-largest-element-in-an-array.rb 215 Apr 4, 2019
216.combination-sum-iii.rb 216 Apr 22, 2019
218.the-skyline-problem.rb
22.generate-parentheses.rb 22 May 8, 2019
226.invert-binary-tree.rb 226 Mar 31, 2019
228.summary-ranges.rb
23.merge-k-sorted-lists.rb 23 Apr 4, 2019
230.kth-smallest-element-in-a-bst.rb 230 Apr 22, 2019
234.palindrome-linked-list.rb 234 Apr 12, 2019
235.lowest-common-ancestor-of-a-binary-search-tree.rb 235 Mar 31, 2019
236.lowest-common-ancestor-of-a-binary-tree.rb 236 Mar 31, 2019
237.delete-node-in-a-linked-list.rb
238.product-of-array-except-self.rb
239.sliding-window-maximum.rb 239 Apr 23, 2019
240.search-a-2d-matrix-ii.rb 240 Mar 31, 2019
242.valid-anagram.rb
243.shortest-word-distance.rb 243 Apr 10, 2019
25.reverse-nodes-in-k-group.rb 25 Apr 13, 2019
252.meeting-rooms.rb
253.meeting-rooms-ii.rb
256.paint-house.rb 256 Apr 10, 2019
26.remove-duplicates-from-sorted-array.rb
266.palindrome-permutation.rb
269.alien-dictionary.rb
276.paint-fence.rb 276 Apr 10, 2019
28.implement-strstr.rb 28 May 8, 2019
280.wiggle-sort.rb 280 Apr 22, 2019
285.inorder-successor-in-bst.rb 285 Apr 7, 2019
29.divide-two-integers.rb
292.nim-game.rb
295.find-median-from-data-stream.rb 295 Mar 31, 2019
297.serialize-and-deserialize-binary-tree.rb 297 Apr 22, 2019
3.longest-substring-without-repeating-characters.rb 3 Mar 31, 2019
300.longest-increasing-subsequence.rb 300 Apr 25, 2019
303.range-sum-query-immutable.rb 303 Mar 31, 2019
307.range-sum-query-mutable.rb 307 Mar 31, 2019
31.next-permutation.rb 31 Apr 3, 2019
315.count-of-smaller-numbers-after-self.rb 315 Mar 31, 2019
32.longest-valid-parentheses.rb 32 Mar 31, 2019
322.coin-change.rb 322 Mar 31, 2019
327.count-of-range-sum.rb
33.search-in-rotated-sorted-array.rb 33 Mar 31, 2019
336.palindrome-pairs.rb
337.house-robber-iii.rb 337 Apr 6, 2019
339.nested-list-weight-sum.rb 339 Apr 10, 2019
34.find-first-and-last-position-of-element-in-sorted-array.rb 34 May 8, 2019
344.reverse-string.rb
346.moving-average-from-data-stream.rb 346 Apr 10, 2019
347.top-k-frequent-elements.rb 347 Apr 4, 2019
35.search-insert-position.rb 35 May 8, 2019
36.valid-sudoku.rb 36 Apr 12, 2019
371.sum-of-two-integers.rb
378.kth-smallest-element-in-a-sorted-matrix.rb
380.insert-delete-getrandom-o1.rb 380 Apr 11, 2019
381.insert-delete-getrandom-o1-duplicates-allowed.rb
384.shuffle-an-array.rb 384 May 14, 2019
387.first-unique-character-in-a-string.rb
388.longest-absolute-file-path.rb 388 Apr 22, 2019
39.combination-sum.rb
4.median-of-two-sorted-arrays.rb
40.combination-sum-ii.rb
409.longest-palindrome.rb
41.first-missing-positive.rb 41 May 12, 2019
416.partition-equal-subset-sum.rb
42.trapping-rain-water.rb
437.path-sum-iii.rb 437 Mar 31, 2019
44.wildcard-matching.rb 44 May 12, 2019
442.find-all-duplicates-in-an-array.rb 442 Apr 25, 2019
445.add-two-numbers-ii.rb 445 Apr 24, 2019
449.serialize-and-deserialize-bst.rb 449 Apr 23, 2019
45.jump-game-ii.rb 45 Apr 1, 2019
450.delete-node-in-a-bst.rb
451.sort-characters-by-frequency.rb 451 Apr 23, 2019
46.permutations.rb 46 Apr 22, 2019
460.lfu-cache.rb 460 Apr 11, 2019
461.hamming-distance.rb 461 Mar 31, 2019
47.permutations-ii.rb 47 Apr 22, 2019
48.rotate-image.rb 48 Apr 11, 2019
49.group-anagrams.rb
493.reverse-pairs.rb
5.longest-palindromic-substring.rb 5 Mar 31, 2019
50.powx-n.rb
509.fibonacci-number.rb 509 Apr 22, 2019
51.n-queens.rb
515.find-largest-value-in-each-tree-row.rb 515 Apr 22, 2019
516.longest-palindromic-subsequence.rb 516 Apr 25, 2019
518.coin-change-2.rb 518 Mar 31, 2019
52.n-queens-ii.rb 52 Apr 3, 2019
523.continuous-subarray-sum.rb
53.maximum-subarray.rb
535.encode-and-decode-tinyurl.rb 535 Apr 22, 2019
54.spiral-matrix.rb 54 Apr 1, 2019
548.split-array-with-equal-sum.rb 548 Mar 31, 2019
55.jump-game.rb 55 Apr 1, 2019
56.merge-intervals.rb
560.subarray-sum-equals-k.rb
57.insert-interval.rb
572.subtree-of-another-tree.rb 572 Apr 22, 2019
587.erect-the-fence.rb
59.spiral-matrix-ii.rb 59 Apr 1, 2019
6.zigzag-conversion.rb
61.rotate-list.rb 61 Apr 22, 2019
617.merge-two-binary-trees.rb 617 Apr 22, 2019
62.unique-paths.rb 62 Mar 31, 2019
63.unique-paths-ii.rb 63 Mar 31, 2019
66.plus-one.rb 66 Apr 5, 2019
661.image-smoother.rb 661 Apr 23, 2019
666.path-sum-iv.rb 666 Mar 31, 2019
673.number-of-longest-increasing-subsequence.rb 673 Apr 25, 2019
674.longest-continuous-increasing-subsequence.rb 674 Apr 25, 2019
678.valid-parenthesis-string.rb 678 Mar 31, 2019
69.sqrtx.rb 69 Apr 8, 2019
694.number-of-distinct-islands.rb
695.max-area-of-island.rb 695 Mar 31, 2019
7.reverse-integer.rb
70.climbing-stairs.rb
701.insert-into-a-binary-search-tree.rb
704.binary-search.rb 704 Apr 22, 2019
706.design-hashmap.rb 706 Mar 31, 2019
718.maximum-length-of-repeated-subarray.rb 718 Apr 26, 2019
719.find-k-th-smallest-pair-distance.rb 719 Apr 11, 2019
72.edit-distance.rb 72 Apr 26, 2019
73.set-matrix-zeroes.rb 73 May 12, 2019
733.flood-fill.rb 733 May 12, 2019
74.search-a-2d-matrix.rb 74 Mar 31, 2019
743.network-delay-time.rb
75.sort-colors.rb 75 Apr 22, 2019
76.minimum-window-substring.rb 76 Apr 12, 2019
765.couples-holding-hands.rb 765 Mar 31, 2019
78.subsets.rb 78 Apr 22, 2019
783.minimum-distance-between-bst-nodes.rb 783 Mar 31, 2019
787.cheapest-flights-within-k-stops.rb 787 Apr 10, 2019
79.word-search.rb 79 Apr 22, 2019
790.domino-and-tromino-tiling.rb 790 Apr 22, 2019
8.string-to-integer-atoi.rb 8 Apr 22, 2019
80.remove-duplicates-from-sorted-array-ii.rb 80 Apr 25, 2019
81.search-in-rotated-sorted-array-ii.rb 81 Mar 31, 2019
812.largest-triangle-area.rb
836.rectangle-overlap.rb 836 Apr 12, 2019
84.largest-rectangle-in-histogram.rb 84 May 12, 2019
862.shortest-subarray-with-sum-at-least-k.rb
863.all-nodes-distance-k-in-binary-tree.rb 863 Mar 31, 2019
876.middle-of-the-linked-list.rb 876 Apr 12, 2019
88.merge-sorted-array.rb
89.gray-code.rb 89 Apr 22, 2019
9.palindrome-number.rb 9 Apr 7, 2019
91.decode-ways.rb 91 Mar 31, 2019
938.range-sum-of-bst.rb 938 Mar 31, 2019
94.binary-tree-inorder-traversal.rb 94 Apr 22, 2019
947.most-stones-removed-with-same-row-or-column.rb 947 Apr 10, 2019
958.check-completeness-of-a-binary-tree.rb
973.k-closest-points-to-origin.rb 973 Mar 31, 2019
98.validate-binary-search-tree.rb 98 Mar 31, 2019
980.unique-paths-iii.rb 980 Mar 31, 2019
99.recover-binary-search-tree.rb 99 Apr 5, 2019
README.org README Apr 24, 2019

README.org

Table of Contents

leetcode-ruby

What are those

These are my leetcode solutions along with some other stuff:

  • Each id.problem_title.rb is a leetcode solution in ruby.
  • other contains problems which are not on leetcode.
  • data-structures contains the general data structures I use to solve problems. They are used throughout my solutions.

What you get

  • Solutions have problem description with it so that you don’t need to visit leetcode. You can also use this repo with leetcode-cli. If you are using Emacs, you can use my plugin lain-leetcode.el.
  • Well documented code, see 4.median-of-two-sorted-arrays.rb for an example.
  • Some problems are difficult to understand if I just shove the optimal solution in your face, therefore I write my thought process and code evolving process, see 10.regular-expression-matching.rb for an example.
  • Well written code, maybe? Coming from FP and OOP background, I tend to write concise function and class with clean API.

Ruby

Ruby, as Matz said, really is a programming language that makes my happy (with leetcode problems of course, being a dynamically typed language after all). But Ruby is not the language to solve intense problems on codeforces or spoj, you’ll get TLE most of the time. However I like to prototype using Ruby for its easy-to-write nature, then rewrite in C/C++.

Ruby arrays are dynamic, it’s kind of like C++’s std::vector or Java’s ArrayList. Its shift (delete at beginning), unshift (insert at beginning), push (insert at end) and pop (delete at end) are amortized O(1) ops. With those amortized O(1) ops it can simulate stack and queue:

Stack

stack = []
stack << 2    # push 2 => stack = [2]
stack << 3    # push 3 => stack = [2, 3]
stack.pop     # pop  3 => stack = [2]

Queue

queue = []
queue << 2    # push 2 => queue = [2]
queue << 3    # push 3 => queue = [2, 3]
queue.shift   # pop  2 => queue = [3]

Map

Maps in ruby are hashes:

map = {}           # empty map
map = Hash.new(0)  # or a map with a default value of 0
map[:a] = 1        # map = {a:1}
map[:b] = 2        # map = {a:1,b:2}

Set

set = Set.new      # empty set
set << 1           # set = #{1}
set << 2           # set = #{1,2}
set << 1           # set = #{1,2}

Other Data Structures

Other data structures such as Priority Queue, Heap, BST, Ruby doesn’t have them build-in, so I implement them when I need to, see data-structures directory:

  • uniou-find.rb Union Find (weighed quick-union with path compression).
  • heap.rb Min Heap, Max Heap and Priority Queue.
  • fenwick-tree.rb 1d Fenwick Tree with range sum query.
  • segment-tree.rb 1d Segment Tree with various query examples.
  • sparse-table.rb 1d Sparse Table with range minimum/maximum query.
  • treap.rb Treap (rotation based and merge/split based).

Memes

./imgs/meme0.jpg

./imgs/meme1.jpg

./imgs/meme2.jpg

Other Useful Stuff

Algorithm

System design

Other

  • TODO Knight Tour
  • Fair Work Load (Binary Search)
  • TODO HashMap With Expiration Time
You can’t perform that action at this time.