LeetCode Solutions in Rust 🦀

A collection of LeetCode problem solutions implemented in Rust, with a focus on clean code and detailed explanations.

📊 Progress

• Total Solved: 169 problems
  • Easy: 27 (16.0%) 🟢
  • Medium: 115 (68.0%) 🟡
  • Hard: 27 (16.0%) 🔴

🌟 Featured Solutions

Here are some noteworthy solutions with interesting approaches:

1. Regular Expression Matching (Hard)

   • Uses dynamic programming
   • Complex pattern matching implementation
   • 98th percentile runtime performance

2. Sliding Window Maximum (Hard)

   • Implements a monotonic queue
   • O(n) time complexity solution
   • Detailed explanation of the algorithm

3. Two Sum (Easy)

   • Classic hash table approach
   • Optimal space-time trade-off
   • Perfect for beginners

📁 Repository Structure

leetcode/
├── problems/
│   └── id_*/ (Solution directories)
│       ├── src/
│       │   └── main.rs (Solution implementation)
│       └── Cargo.toml
├── leetcode_cli/ (Project creation tool)
└── update_readme/ (README update script)

🛠️ Tools & Utilities

LeetCode CLI

A command-line tool for quickly creating new solution projects:

new_leetcode 1234 --difficulty Medium --tags "array,dp" --title "Problem Title"

Learn more about LeetCode CLI

Automatic README Updates

This repository uses a pre-commit hook to automatically update the README.md file whenever changes are committed. The system includes:

1. update_readme - A Rust script that:

   • Scans the problems directory
   • Extracts solution metadata
   • Updates statistics
   • Generates the solutions table
   • Updates the README.md file

2. Pre-commit Hook Setup

   • Add the following script to .git/hooks/pre-commit:

   #!/usr/bin/env bash
   # run the `./update_readme/target/release/update_readme` binary to update the README.md
   # when files in `./problems/id_*` are changed.
   
   # get the list of files that have been changed
   # since the last commit
   files=$(git diff --cached --name-only)
   
   # check if any of the files are in the `./problems/id_*` directory
   if [[ $files == *"problems/id_"* ]]; then
       # if so, run the `update_readme` binary
       ./update_readme/target/release/update_readme
       # add the changes to the commit
       git add README.md
   fi
   
   # continue with the commit
   exit 0

   Make sure to give the script execution permissions:

   chmod +x .git/hooks/pre-commit

The script will run automatically before each commit, ensuring the README is always up to date with:

• Current solution count and statistics
• Complete solutions table
• Difficulty distribution

📝 Solution Format

Each solution includes this header format for easy navigation and reference (and for the readme generator to parse):

///
/// # Problem Title (Difficulty) [Tag1, Tag2]
/// LeetCode Problem {id}
///

📋 Solutions Table

ID	Title	Difficulty	Tags
1	Two sums	Easy	Array, Hash Table
7	Reverse Integer	Medium	Math
9	Palindrome Number	Easy	Math
10	Regular Expression Matching	Hard	String, Dynamic Programming, Recursion
12	Integer to Roman	Medium	Hash Table, Math, String
20	Valid Parentheses	Easy	String, Stack
22	Generate Parentheses	Medium	String, Dynamic Programming, Backtracking
29	Divide Two Integers	Medium	Math, Bit Manipulation
37	Sudoku Solver	Hard	Array, Hash Table, Backtracking, Matrix
239	Sliding Window Maximum	Hard	Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue
273	Integer to English Words	Hard	Math, String, Recursion
407	Trapping Rain Water II	Hard	Array, Breadth First Search, Heap (priority Queue), Matrix
494	Target Sum	Medium	Array, Dynamic Programming, Backtracking
515	Find Largest Value in Each Tree Row	Medium	Tree, Depth First Search, Breadth First Search, Binary Tree
567	Permutation in String	Medium	Hash Table, Two Pointers, String, Sliding Window
670	Maximum Swap	Medium	Math, Greedy
684	Redundant Connection	Medium	Depth First Search, Breadth First Search, Union Find, Graph
689	Maximum Sum of 3 Non-Overlapping Subarrays	Hard	Array, Dynamic Programming
729	My Calendar I	Medium	Array, Binary Search, Design, Segment Tree, Ordered Set
769	Max Chunks To Make Sorted	Medium	Array, Stack, Greedy, Sorting, Monotonic Stack
773	Sliding Puzzle	Hard	Array, Breadth First Search, Matrix
796	Rotate String	Easy	String, String Matching
802	Find Eventual Safe States	Medium	Depth First Search, Breadth First Search, Graph, Topological Sort
827	Making A Large Island	Hard	Array, Depth First Search, Breadth First Search, Union Find, Matrix
862	Shortest Subarray with Sum at Least K	Hard	Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue
873	Length of Longest Fibonacci Subsequence	Medium	Array, Hash Table, Dynamic Programming
889	Construct Binary Tree from Preorder and Postorder Traversal	Medium	Array, Hash Table, Divide And Conquer, Tree, Binary Tree
916	Word Subsets	Medium	Array, Hash Table, String
921	Minimum Add to Make Parentheses Valid	Medium	String, Stack, Greedy
951	Minimum Add to Make Parentheses Valid	Medium	String, Stack, Greedy
962	Maximum Width Ramp	Medium	Array, Stack, Monotonic Stack
983	Minimum Cost For Tickets	Medium	Array, Dynamic Programming
1014	Best Sightseeing Pair	Medium	Array, Dynamic Programming
1028	Recover a Tree From Preorder Traversal	Hard	String, Tree, Depth First Search, Binary Tree
1072	Flip Columns For Maximum Number of Equal Rows	Medium	Array, Hash Table, Matrix
1079	Letter Tile Possibilities	Medium	Hash Table, String, Backtracking, Counting
1092	Shortest Common Supersequence	Hard	String, Dynamic Programming
1106	Parsing A Boolean Expression	Hard	String, Stack, Recursion
1233	Remove Sub-Folders from the Filesystem	Medium	Array, String, Depth-First Search, Trie
1261	Find Elements in a Contaminated Binary Tree	Medium	Hash Table, Tree, Depth First Search, Breadth First Search, Design, Binary Tree
1267	Count Servers that Communicate	Medium	Array, Depth First Search, Breadth First Search, Union Find, Matrix, Counting
1277	Count Square Submatrices with All Ones	Medium	Array, Dynamic Programming, Matrix
1331	Rank Transform of an Array	Easy	Array, Hash Table, Sorting
1346	Check If N and Its Double Exist	Easy	Array, Hash Table, Two Pointers, Binary Search, Sorting
1352	Product of the Last K Numbers	Medium	Array, Math, Design, Data Stream, Prefix Sum
1368	Minimum Cost to Make at Least One Valid Path in a Grid	Hard	Array, Breadth First Search, Graph, Heap (priority Queue), Matrix, Shortest Path
1400	Construct K Palindrome Strings	Medium	Hash Table, String, Greedy, Counting
1405	Longest Happy String	Medium	String, Greedy, Heap (Priority Queue)
1408	String Matching in an Array	Easy	Array, String, String Matching
1415	The k-th Lexicographical String of All Happy Strings of Length n	Medium	String, Backtracking
1422	Maximum Score After Splitting a String	Easy	String, Prefix Sum
1455	Check If a Word Occurs As a Prefix of Any Word in a Sentence	Easy	Two Pointers, String, String Matching
1462	Course Schedule IV	Medium	Depth First Search, Breadth First Search, Graph, Topological Sort
1475	Final Prices With a Special Discount in a Shop	Easy	Array, Stack, Monotonic Stack
1497	Check If Array Pairs Are Divisible by k	Medium	Array, Hash Table, Counting
1524	Number of Sub-arrays With Odd Sum	Medium	Array, Math, Dynamic Programming, Prefix Sum
1545	Find Kth Bit in Nth Binary String	Medium	String, Recursion, Simulation
1574	Shortest Subarray to be Removed to Make Array Sorted	Medium	Array, Two Pointers, Binary Search, Stack, Monotonic Stack
1590	Make Sum Divisible by P	Medium	Array, Hash Table, Prefix Sum
1593	Split a String Into the Max Number of Unique Substrings	Medium	Hash Table, String, Backtracking
1639	Number of Ways to Form a Target String Given a Dictionary	Hard	Array, String, Dynamic Programming
1652	Defuse the Bomb	Easy	Array, Sliding Window
1671	Minimum Number of Removals to Make Mountain Array	Hard	Array, Binary Search, Dynamic Programming, Greedy
1718	Construct the Lexicographically Largest Valid Sequence	Medium	Array, Backtracking
1726	Tuple with Same Product	Medium	Array, Hash Table, Counting
1749	Maximum Absolute Sum of Any Subarray	Medium	Array, Dynamic Programming
1752	Check if Array Is Sorted and Rotated	Easy	Array
1760	Minimum Limit of Balls in a Bag	Medium	Array, Binary Search
1765	Map of Highest Peak	Medium	Array, Breadth First Search, Matrix
1769	Minimum Number of Operations to Move All Balls to Each Box	Medium	Array, String, Prefix Sum
1780	Check if Number is a Sum of Powers of Three	Medium	Math
1790	Check if One String Swap Can Make Strings Equal	Easy	Hash Table, String, Counting
1792	Maximum Average Pass Ratio	Medium	Array, Greedy, Heap (Priority Queue)
1800	Maximum Ascending Subarray Sum	Easy	Array
1813	Sentence Similarity III	Medium	Array, Two Pointers, String
1829	Maximum XOR for Each Query	Medium	Array, Bit Manipulation, Prefix Sum
1861	Rotating the Box	Medium	Array, Two Pointers, Matrix
1910	Remove All Occurrences of a Substring	Medium	String, Stack, Simulation
1930	Unique Length-3 Palindromic Subsequences	Medium	Hash Table, String, Bit Manipulation, Prefix Sum
1942	The Number of the Smallest Unoccupied Chair	Medium	Array, Hash Table, Heap (Priority Queue)
1957	Delete Characters to Make Fancy String	Easy	String
1963	Minimum Number of Swaps to Make the String Balanced	Medium	Two Pointers, String, Stack, Greedy
1975	Maximum Matrix Sum	Medium	Array, Greedy, Matrix
1980	Find Unique Binary String	Medium	Array, Hash Table, String, Backtracking
2017	Grid Game	Medium	Array, Matrix, Prefix Sum
2044	Count Number of Maximum Bitwise-OR Subsets	Medium	Array, Backtracking, Bit Manipulation, Enumeration
2054	Two Best Non-Overlapping Events	Medium	Array, Binary Search, Dynamic Programming, Sorting, Heap (priority Queue)
2064	Minimized Maximum of Products Distributed to Any Store	Medium	Array, Binary Search
2070	Most Beautiful Item for Each Query	Medium	Array, Binary Search, Sorting
2097	Valid Arrangement of Pairs	Hard	Depth First Search, Graph, Eulerian Circuit
2109	Adding Spaces to a String	Medium	Array, Two Pointers, String, Simulation
2116	Check if a Parentheses String Can Be Valid	Medium	String, Stack, Greedy
2127	Maximum Employees to Be Invited to a Meeting	Hard	Depth First Search, Graph, Topological Sort
2161	Partition Array According to Given Pivot	Medium	Array, Two Pointers, Simulation
2182	Construct String With Repeat Limit	Medium	Hash Table, String, Greedy, Heap (priority Queue), Counting
2185	Counting Words With a Given Prefix	Easy	Array, String, String Matching
2222	Number of Ways to Select Buildings	Medium	String, Dynamic Programming, Prefix Sum
2257	Count Unguarded Cells in the Grid	Medium	Array, Matrix, Simulation
2270	Number of Ways to Split Array	Medium	Array, Prefix Sum
2275	Largest Combination With Bitwise AND Greater Than Zero	Medium	Array, Hash Table, Bit Manipulation, Counting
2290	Minimum Obstacle Removal to Reach Corner	Hard	Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path
2335	Moving Pieces to Obtain a String	Medium	String, Two Pointers
2342	Max Sum of a Pair With Equal Sum of Digits	Medium	Array, Hash Table, Sorting, Heap (priority Queue)
2349	Design a Number Container System	Medium	Hash Table, Design, Heap (priority Queue), Ordered Set
2364	Count Number of Bad Pairs	Medium	Array, Hash Table, Math, Counting
2375	Construct Smallest Number From DI String	Medium	String, Backtracking, Stack, Greedy
2381	Shifting Letters II	Medium	Array, String, Prefix Sum
2415	Reverse Odd Levels of Binary Tree	Medium	Tree, Depth First Search, Breadth First Search, Binary Tree
2416	Sum of Prefix Scores of Strings	Hard	Array, String, Trie, Counting
2423	Remove Letter To Equalize Frequency	Easy	Hash Table, String, Counting
2425	Bitwise XOR of All Pairings	Medium	Array, Bit Manipulation, Brainteaser
2429	Minimize XOR	Medium	Greedy, Bit Manipulation
2458	Height of Binary Tree After Subtree Removal Queries	Hard	Array, Tree, Depth-First Search, Breadth-First Search, Binary Tree
2460	Apply Operations to an Array	Easy	Array, Two Pointers, Simulation
2461	Maximum Sum of Distinct Subarrays With Length K	Medium	Array, Hash Table, Sliding Window
2463	Minimum Total Distance Traveled	Hard	Array, Dynamic Programming, Sorting
2466	Count Ways To Build Good Strings	Medium	Dynamic Programming
2467	Most Profitable Path in a Tree	Medium	Array, Tree, Depth First Search, Breadth First Search, Graph
2471	Minimum Number of Operations to Sort a Binary Tree by Level	Medium	Tree, Breadth First Search, Binary Tree
2490	Circular Sentence	Easy	String
2493	Divide Nodes Into the Maximum Number of Groups	Hard	Breadth First Search, Union Find, Graph
2501	Longest Square Streak in an Array	Medium	Array, Hash Table, Binary Search, Dynamic Programming, Sorting
2516	Take K of Each Character From Left and Right	Medium	Hash Table, String, Sliding Window
2554	Maximum Number of Integers to Choose From a Range I	Medium	Array, Hash Table, Binary Search, Greedy, Sorting
2558	Take Gifts From the Richest Pile	Easy	Array, Heap (priority Queue), Simulation
2559	Count Vowel Strings in Ranges	Medium	Array, String, Prefix Sum
2563	Count the Number of Fair Pairs	Medium	Array, Two Pointers, Binary Search, Sorting
2570	Merge Two 2D Arrays by Summing Values	Easy	Array, Hash Table, Two Pointers
2577	Minimum Time to Visit a Cell In a Grid	Hard	Array, Breadth First Search, Graph, Heap (priority Queue), Matrix, Shortest Path
2579	Count Total Number of Colored Cells	Medium	Math
2583	Kth Largest Sum in a Binary Tree	Medium	Tree, Breadth-First Search, Sorting, Binary Tree
2593	Find Score of an Array After Marking All Elements	Medium	Array, Hash Table, Sorting, Heap (priority Queue), Simulation
2601	Prime Subtraction Operation	Medium	Array, Math, Binary Search, Greedy, Number Theory
2641	Cousins in Binary Tree II	Medium	Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
2657	Find the Prefix Common Array of Two Arrays	Medium	Array, Hash Table, Bit Manipulation
2658	Maximum Number of Fish in a Grid	Medium	Array, Depth First Search, Breadth First Search, Union Find, Matrix
2661	First Completely Painted Row or Column	Medium	Array, Hash Table, Matrix
2683	Neighboring Bitwise XOR	Medium	Array, Bit Manipulation
2684	Maximum Number of Moves in a Grid	Medium	Array, Dynamic Programming, Matrix
2696	Minimum String Length After Removing Substrings	Easy	String, Stack, Simulation
2698	Find the Punishment Number of an Integer	Medium	Math, Backtracking
2762	Continuous Subarrays	Medium	Array, Queue, Sliding Window, Heap (priority Queue), Ordered Set, Monotonic Queue
2779	Maximum Beauty of an Array After Applying Operation	Medium	Array, Binary Search, Sliding Window, Sorting
2825	Make String a Subsequence Using Cyclic Increments	Medium	Two Pointers, String
2872	Maximum Number of K-Divisible Components	Hard	Tree, Depth First Search
2914	Minimum Changes to Make Binary String Beautiful	Medium	String
2924	Find Champion II	Medium	Graph
2938	Separate Black and White Balls	Medium	Two Pointers, String, Greedy
2940	Find Building Where Alice and Bob Can Meet	Hard	Array, Binary Search, Stack, Monotonic Stack
2948	Make Lexicographically Smallest Array by Swapping Elements	Medium	Array, Union Find, Sorting
2981	Find Longest Special Substring That Occurs Thrice I	Medium	Hash Table, String, Binary Search, Sliding Window, Counting
3011	Find if Array Can Be Sorted	Medium	Array, Bit Manipulation, Sorting
3017	Count the Number of Houses at a Certain Distance II	Hard	Graph, Prefix Sum
3042	Count Prefix and Suffix Pairs I	Easy	Array, String, Trie, Rolling Hash, String Matching, Hash Function
3043	Find the Length of the Longest Common Prefix	Medium	Array, Hash Table, String, Trie
3066	Minimum Operations to Exceed Threshold Value II	Medium	Array, Heap (priority Queue), Simulation
3090	Shortest Subarray With OR at Least K II	Medium	Array, Bit Manipulation, Sliding Window
3105	Longest Strictly Increasing or Strictly Decreasing Subarray	Easy	Array
3133	Minimum Array End	Medium	Bit Manipulation
3151	Special Array I	Easy	Array
3152	Special Array II	Medium	Array, Binary Search, Prefix Sum
3160	Find the Number of Distinct Colors Among the Balls	Medium	Array, Hash Table, Simulation
3163	String Compression III	Medium	String
3174	Clear Digits	Easy	String, Stack, Simulation
3203	Find Minimum Diameter After Merging Two Trees	Hard	Tree, Depth First Search, Breadth First Search, Graph
3223	Minimum Length of String After Operations	Medium	Hash Table, String, Counting
3243	Shortest Distance After Road Addition Queries I	Medium	Array, Breadth First Search, Graph
3254	Find the Power of K-Size Subarrays I	Medium	Array, Sliding Window
3264	Final Array State After K Multiplication Operations I	Easy	Array, Math, Heap (priority Queue), Simulation

🚀 Getting Started

1. Clone the repository:

git clone https://github.com/tomPlanche/leetcode.git

2. Navigate to a solution:

cd problems/id_<problem_number>

3. Run the solution:

cargo run

📄 License

This project is licensed under the MIT License - see the LICENSE file for details.

👤 Author

Tom Planche

• GitHub: @tomPlanche
• LinkedIn: Tom Planche