chuchunf/leetcode-scala-3

LeetCode Solutions in Scala 3

LeetCode-Scala-3

Solutions of selected LeetCode problems in Scala 3.

Goal

• Learn Scala 3 :)
• Practise Algorithm :)

Code

• Try to be compact and readable at the same time
• Try Scala 3 syntax and features but with less Scala specific libraries

Solutions

List of Problems by topic and category

• Solutions are organized into topics, following the same grouping as LeetCode
• Topics are further divided into categories
• Solutions in each Topic/Category are ordered by difficulty level
• Solutions with more explanation are bold

Topic	Category	Problem List
Hashmap	Check existence with O(1)	1. Two Sum 387. First unique character in a string 202. Happy Number
	Discrete key/value container for further processing	205. Isomorphic Strings 299. Bulls and Cows 554. Brick Wall
	Implementation and other usages	380. Insert Delete GetRandom O(1)
OrderedSet	Get a key based on predefined order	729. My Calendar I 731. My Calendar II 1818. Minimum Absolute Sum Difference
	A compact ordered container	855. Exam Room 732. My Calendar III
LinkedList	Basic operation	206. Reverse Linked List 61. Rotate List 143. Reorder List 86. Partition List
	Additional operation	19. Remove Nth Node From End of List 83. Remove Duplicates from Sorted List 82. Remove Duplicates from Sorted List II 138. Copy List with Random Pointer
	Use of linked list	2. Add Two Numbers 445. Add Two Numbers 2
	Others	160. Intersection of Two Linked Lists
Two Pointers	Sliding windows	219. Contains Duplicate II 30. Substring with Concatenation of All Words
	Two Pointers: same direction	228. Summary Ranges 3. Longest Substring Without Repeating Characters 28. Implement strStr() 159. Longest Substring with At Most Two Distinct Characters 80. Remove Duplicates from Sorted Array II 209. Minimum Size Sub array Sum 443. String Compression
	Two Pointers: opposite direction	125. Valid Palindrome 2330. Valid Palindrome IV 680. Valid Palindrome II 167. Two Sum II 75. Sort Colors 16. 3Sum Closest 15. 3Sum 11. Container With Most Water 42. Trapping Rain Water
Fast Slow Pointers		876. Middle of the Linked List 141. Linked List Cycle 142. Linked List Cycle II
String	General Operations	14. Longest Common Prefix 415. Add Strings 67. Add Binary 38. Count and Say 6. ZigZag Conversion 165. Compare Version Numbers
	Other Algorithms	763. Partition Labels 161. One Edit Distance 76. Minimum Window Substring
Number		9. Palindrome Number 7. Reverse Integer 43. Multiply Strings
Counting		217. Contains Duplicate 383. Ransom Note 169. Majority Element 229. Majority Element 2 358. Rearrange String k Distance Apart
Math	Conversion	12. Integer to Roman 13. Roman to Integer 168. Excel Sheet Column Title 171. Excel Sheet Column Number 166. Fraction to Recurring Decimal
	Calculation	66. Plus One 50. Pow(x, n)
	Tricks	96. Unique Binary Search Trees 172. Factorial Trailing Zeroes
	Geometry	149. Max Points on a Line
Bit	Operations on Bits	405. Convert a Number to Hexadecimal 191. Number of 1 Bits 190. Reverse Bits 89. Gray Code
	Divide and Mod	29. Divide Two Integers 78. Subsets
	Uses of Bit	187. Repeated DNA 136. Single Number 137. Single Number 2
Array	In-place manipulation	26. Remove Duplicates from Sorted Array 283. Move Zeroes
	Swap or reverse	88. Merge Sorted Array 151. Reverse Words in a String 189. Rotate Array
	Others	121. Best Time to Buy and Sell Stock 78. Subsets 945. Minimum Increment to Make Array Unique
Matrix	Basic operations	54. Spiral Matrix 59. Spiral Matrix II 36. Valid Sudoku 74. Search a 2D Matrix
	In-place operations	73. Set Matrix Zero 48. Rotate Image
	Backtracking	37. Sudoku Solver
Binary Search	Basic	35. Search Insert Position 34. Find First and Last Position of Element in Sorted Array 278. First Bad Version 69. Sqrt(x) 275. H-Index II
	Rotated Sorted Array	33. Search in Rotated Sorted Array 81. Search in Rotated Sorted Array II 153. Find Minimum in Rotated Sorted Array 154. Find Minimum in Rotated Sorted Array II
	Two Sorted or Partially Sorted Arrays	162. Find Peak Element 4. Median of Two Sorted Arrays
Prefix Sum	Basic operation 1 way or 2 way	303. Range Sum Query - Immutable 724. Find Pivot Index 238. Product of Array Except Self
	Alternatives and Addons	536. Continuous Subarray Sum 525. Contiguous Array
Stack	Implementation	155. Min Stack
	Backtrack previous element	20. Valid Parentheses 901. Online Stock Span 32. Longest Valid Parentheses 581. Shortest Unsorted Continuous Sub array
	Applications	150. Evaluate Reverse Polish Notation 71. Simplify Path 394. Decode String
Monotonic Stack		496. Next Greater Element I 503. Next Greater Element II 556. Next Greater Element III 84. Largest Rectangle in Histogram
Queue	Implementation	225. Implement Stack using Queues 232. Implement Queue Using Stacks
	FILO order collection	649. Dota2 Senate 281. Zigzag Iterator 950. Reveal Cards In Increasing Order
	Monotonic Queue	239. Sliding Window Maximum
Sort		148. Sort List 49. Group Anagrams 56. Merge Intervals
Bucket Sort	Frequency	347. Top K Frequent Elements 692. Top K Frequent Words 451. Sort Characters By Frequency
	Usage of Bucket	164. Maximum Gap 220. Contains Duplicate III
Recursion	With recursive data structure	21. Merge Two Sorted Lists 23. Merge K Sorted List 24. Swap Nodes in Pairs 25. Reverse Nodes in K-Group 87. Scramble String 10. Regular Expression Matching
	Without recursive data structure	247. Strobogrammatic Number II 60. Permutation Sequence
Tree	Tree Traversals	144. Binary Tree Preorder Traversal 94. Binary Tree Inorder Traversal 145. Binary Tree Postorder Traversal 102. Binary Tree Level Order Traversal 103. Binary Tree Zigzag Level Order Traversal
	Other operations	226. Invert Binary Tree
	Check Tree properties	110. Balanced Binary Tree 101. Symmetric Tree 104. Maximum Depth of Binary Tree 111. Minimum Depth of Binary Tree 236. Lowest Common Ancestor of a Binary Tree
	Construction and Destruction of Tree	114. Flatten Binary Tree to Linked List 105. Construct Binary Tree from Preorder and Inorder Traversal 106. Construct Binary Tree from Inorder and Postorder Traversal
Tries		208. Implement Tries 139. Word Break 140. Word Break 2 212. Word Search 2 1065. Index Pairs of a String
Binary Search Tree	Check BST properties	98. Validate Binary Search Tree 100. Same Tree 235. Lowest Common Ancestor of a Binary Search Tree
	Modify BST	450. Delete Node in a BST 701. Insert into a Binary Search Tree
	Construct BST	108. Convert Sorted Array to Binary Search Tree 173. Binary Search Tree Iterator
	Traversal of BST	99. Recover Binary Search Tree 257. Binary Tree Paths
DFS	Recursion	112. Path Sum 116. Populating Next Right Pointers in Each Node 129. Sum Root to Leaf Numbers 156. Binary Tree upside Down 113. Path Sum II
	Back tracking	113. Path Sum II 127. Word Ladder
BFS		199. Binary Tree Right Side View 133. Clone Graph 130. Surrounded Regions
Graph		207. Course Schedule 210. Course Schedule II 310. Minimum Height Trees
Union Find		200. Number of Islands 305. Number of Islands II 547. Number of Provinces
Heap		506. Relative Ranks 264. Ugly Number II 215. Kth Largest Element in an Array 23. Merge K sorted list 218. The Skyline
Back Tracking		22. Generate Parentheses 40. Combination Sum II 46. Permutations 17. Letter Combinations of a Phone Number 47. Permutations II 77. Combinations 79. Word Search 93. Restore IP Addresses 51. N-Queens 52. N-Queens 2
Dynamic Programming	Count number in array or matrix	70. Climbing Stairs 64. Minimum Path Sum 91. Decode Ways 55. Jump Game 63. Unique Paths 2 120. Triangle 174. Dungeon Game 123. Best Time to Buy and Sell Stock III
	Knapsack and coin machine etc	53. Maximum Subarray 322. Coin Change 518. Coin Change 2 494. Target Sum
	Substring and common string etc	5. Longest Palindromic Substring 97. Interleaving String 115. Distinct Subsequences 516. Longest Palindromic Subsequence 1216. Valid Palindrome III
Greedy		122. Best Time to Buy and Sell Stock II 134. Gas Station 179. Largest Number 44. Wildcard Matching 135. Candy 630. Course Schedule III

List of Problems by Series

• Problems grouped into series, each series has a common setting but different constraints.
• Different data structures and algorithms could be used to handle these constraints accordingly.

Series	Problem List
My Calendar	729. My Calendar I 731. My Calendar II 732. My Calendar III
Contains Duplicate	217. Contains Duplicate 219-contains-duplicate-ii 220-contains-duplicate-iii
Valid Palindrome	125. Valid Palindrome 2330. Valid Palindrome IV 680. Valid Palindrome II 1216. Valid Palindrome III
Next Greater Element	496. Next Greater Element 503. Next Greater Element II 556. Next Greater Element III
Course Schedule	207. Course Schedule 210. Course Schedule II 603. Course Schedule III
Best Time to Buy and Sell Stock	121. Best Time to Buy and Sell Stock 122. Best Time to Buy and Sell Stock II 123. Best Time to Buy and Sell Stock III 188. Best Time to Buy and Sell Stock IV