Solutions, unit tests, and code skeletons for problems from Leetcode OJ. (in progress)

  root
    |--- doc
    |     |-- category.md   // category for problems in leetcode
    |     |-- problems.tsv  // searchable tsv file listing problems from leetcode
    |     |-- road.md       // general things I learnt through the process
    |--- lib
    |     |-- *.jar         // jar file referenced in this project
    |--- src   // solutions for problems
    |     |-- _001_TwoSum
    |     |         |-- Practice.java    // code skeleton
    |     |         |-- Solution.java
    |     |         |-- Solution*.java   // other solutions for this problem
    |     |-- ......
    |--- test  // unit tests
    |     |-- _001_TwoSum
    |     |         |-- PracticeTest.java 
    |     |         |-- SolutionTest.java
    |     |         |-- Solution*Test.java
    |     |-- ......

• Discussions and code reviews are more than welcome.
• Solution.java provides OJ-accepted solution.
• Practice.java provides code skeleton for each problem
• SolutionTest.java and PracticeTest.java provides basic unit tests to verify your solution.

P.S.:

• Please use Java 8 to compile and run
• Many solutions are from online sources, like Leetcode OJ discussion, coders' blogs, etc.
• Solution that passed unit tests does not guarantee to pass Leetcode OJ.

#	Problem	Difficulty	Tags	Note
001	Two Sum	Medium	Array Hash Table	O(N^2) -> O(N) + O(N) hashtable
002	Add Two Numbers	Medium	Linked List Math
003	Longest Substring Without Repeating Characters	Medium	Hash Table Two Pointers String	two pointers to keep window -> O(N)
004	Median of Two Sorted Arrays	Hard	Divide and Conquer Array Binary Search
005	Longest Palindromic Substring	Medium	String	expanding two pointers
006	ZigZag Conversion	Easy	String
007	Reverse Integer	Easy	Math	How to monitor Stack Overflow
008	String to Integer (atoi)	Easy	Math String
009	Palindrome Number	Easy	Math	1) count digits; 2) get digit from number's front/back; 3) to avoid StackOverflow, only reverse half part of number
010	Regular Expression Matching	Hard	Dynamic Programming Backtracking String	finite state machine!
011	Container With Most Water	Medium	Array Two Pointers	narrowing two pointers
012	Integer to Roman	Medium	Math String
013	Roman to Integer	Easy	Math String
014	Longest Common Prefix	Easy	String
015	3Sum	Medium	Array Two Pointers	sorting then 2sum
016	3Sum Closest	Medium	Array Two Pointers
017	Letter Combinations of a Phone Number	Medium	Backtracking String	BFS: iterative V.S. DFS: backtracking
018	4Sum	Medium	Array Hash Table Two Pointers
019	Remove Nth Node From End of List	Easy	Linked List Two Pointers	fast-slow two pointers on Linked List
020	Valid Parentheses	Easy	Stack String	stack basic, corner case
021	Merge Two Sorted Lists	Easy	Linked List
022	Generate Parentheses	Medium	Backtracking String	BT template
023	Merge k Sorted Lists	Hard	Divide and Conquer Linked List Heap
024	Swap Nodes in Pairs	Medium	Linked List
025	Reverse Nodes in k-Group	Hard	Linked List
026	Remove Duplicates from Sorted Array	Easy	Array Two Pointers	partition techinque on array
027	Remove Element	Easy	Array Two Pointers
028	Implement strStr()	Easy	Two Pointers String
029	Divide Two Integers	Medium	Math Binary Search	!
030	Substring with Concatenation of All Words	Hard	Hash Table Two Pointers String
031	Next Permutation	Medium	Array
032	Longest Valid Parentheses	Hard	Dynamic Programming String	DP
033	Search in Rotated Sorted Array	Hard	Array Binary Search
034	Search for a Range	Medium	Array Binary Search	! one binary search to find start position, and another one find ending position
035	Search Insert Position	Medium	Array Binary Search	standard binary search with minor modification
036	Valid Sudoku	Easy	Hash Table
037	Sudoku Solver	Hard	Backtracking Hash Table
038	Count and Say	Easy	String
039	Combination Sum	Medium	Array Backtracking	BT template + prune siblings
040	Combination Sum II	Medium	Array Backtracking	BT template + prune siblings + skip duplicate
041	First Missing Positive	Hard	Array	swap-until technique
042	Trapping Rain Water	Hard	Array Stack Two Pointers	!!
043	Multiply Strings	Medium	Math String	! simulate multiplication
044	Wildcard Matching	Hard	Dynamic Programming Backtracking Greedy String
045	Jump Game II	Hard	Array Greedy
046	Permutations	Medium	Backtracking	backtrack template + select to add
047	Permutations II	Hard	Backtracking	backtrack template + select to add + skip duplicate using set
048	Rotate Image	Medium	Array
049	Group Anagrams	Medium	Hash Table String	!!
050	Pow(x, n)	Medium	Math Binary Search
051	N-Queens	Hard	Backtracking
052	N-Queens II	Hard	Backtracking
053	Maximum Subarray	Medium	Divide and Conquer Array Dynamic Programming
054	Spiral Matrix	Medium	Array
055	Jump Game	Medium	Array Greedy
056	Merge Intervals	Hard	Array Sort	how to decide the boundary of merged interval
057	Insert Interval	Hard	Array Sort	! enlarge to merge interval
058	Length of Last Word	Easy	String
059	Spiral Matrix II	Medium	Array
060	Permutation Sequence	Medium	Backtracking Math
061	Rotate List	Medium	Linked List Two Pointers	fast-slow pointers; [189] Rotate Array
062	Unique Paths	Medium	Array Dynamic Programming
063	Unique Paths II	Medium	Array Dynamic Programming
064	Minimum Path Sum	Medium	Array Dynamic Programming
065	Valid Number	Hard	Math String
066	Plus One	Easy	Array Math
067	Add Binary	Easy	Math String	add binary numbers
068	Text Justification	Hard	String	! very careful string operations
069	Sqrt(x)	Medium	Math Binary Search	!binary search along y-axle
070	Climbing Stairs	Easy	Dynamic Programming
071	Simplify Path	Medium	Stack String
072	Edit Distance	Hard	Dynamic Programming String
073	Set Matrix Zeroes	Medium	Array
074	Search a 2D Matrix	Medium	Array Binary Search	2D coordidates --> 1D index
075	Sort Colors	Medium	Array Two Pointers Sort
076	Minimum Window Substring	Hard	Hash Table Two Pointers String	![substring/sublist] hashing + two pointers -> O(N)
077	Combinations	Medium	Backtracking
078	Subsets	Medium	Array Backtracking Bit Manipulation	see README
079	Word Search	Medium	Array Backtracking
080	Remove Duplicates from Sorted Array II	Medium	Array Two Pointers	from 2 to k (general)
081	Search in Rotated Sorted Array II	Medium	Array Binary Search
082	Remove Duplicates from Sorted List II	Medium	Linked List
083	Remove Duplicates from Sorted List	Easy	Linked List
084	Largest Rectangle in Histogram	Hard	Array Stack
085	Maximal Rectangle	Hard	Array Hash Table Stack Dynamic Programming
086	Partition List	Medium	Linked List Two Pointers
087	Scramble String	Hard	Dynamic Programming String
088	Merge Sorted Array	Easy	Array Two Pointers	in-place merging -> from end to begin; two pointers on two lists
089	Gray Code	Medium	Backtracking
090	Subsets II	Medium	Array Backtracking	backtrack template + skip duplicate
091	Decode Ways	Medium	Dynamic Programming String
092	Reverse Linked List II	Medium	Linked List
093	Restore IP Addresses	Medium	Backtracking String
094	Binary Tree Inorder Traversal	Medium	Tree Hash Table Stack
095	Unique Binary Search Trees II	Medium	Tree Dynamic Programming
096	Unique Binary Search Trees	Medium	Tree Dynamic Programming
097	Interleaving String	Hard	Dynamic Programming String
098	Validate Binary Search Tree	Medium	Tree Depth-first Search
099	Recover Binary Search Tree	Hard	Tree Depth-first Search
100	Same Tree	Easy	Tree Depth-first Search
101	Symmetric Tree	Easy	Tree Depth-first Search
102	Binary Tree Level Order Traversal	Easy	Tree Breadth-first Search
103	Binary Tree Zigzag Level Order Traversal	Medium	Tree Breadth-first Search Stack
104	Maximum Depth of Binary Tree	Easy	Tree Depth-first Search
105	Construct Binary Tree from Preorder and Inorder Traversal	Medium	Tree Array Depth-first Search
106	Construct Binary Tree from Inorder and Postorder Traversal	Medium	Tree Array Depth-first Search
107	Binary Tree Level Order Traversal II	Easy	Tree Breadth-first Search
108	Convert Sorted Array to Binary Search Tree	Medium	Tree Depth-first Search
109	Convert Sorted List to Binary Search Tree	Medium	Depth-first Search Linked List
110	Balanced Binary Tree	Easy	Tree Depth-first Search
111	Minimum Depth of Binary Tree	Easy	Tree Depth-first Search Breadth-first Search
112	Path Sum	Easy	Tree Depth-first Search
113	Path Sum II	Medium	Tree Depth-first Search
114	Flatten Binary Tree to Linked List	Medium	Tree Depth-first Search
115	Distinct Subsequences	Hard	Dynamic Programming String
116	Populating Next Right Pointers in Each Node	Medium	Tree Depth-first Search
117	Populating Next Right Pointers in Each Node II	Hard	Tree Depth-first Search
118	Pascal's Triangle	Easy	Array
119	Pascal's Triangle II	Easy	Array
120	Triangle	Medium	Array Dynamic Programming
121	Best Time to Buy and Sell Stock	Medium	Array Dynamic Programming	O(N^2) -> O(N)
122	Best Time to Buy and Sell Stock II	Medium	Array Greedy
123	Best Time to Buy and Sell Stock III	Hard	Array Dynamic Programming
124	Binary Tree Maximum Path Sum	Hard	Tree Depth-first Search	post-order, local and global , README
125	Valid Palindrome	Easy	Two Pointers String
126	Word Ladder II	Hard	Array Backtracking Breadth-first Search String
127	Word Ladder	Medium	Breadth-first Search
128	Longest Consecutive Sequence	Hard	Array
129	Sum Root to Leaf Numbers	Medium	Tree Depth-first Search
130	Surrounded Regions	Medium	Breadth-first Search
131	Palindrome Partitioning	Medium	Backtracking
132	Palindrome Partitioning II	Hard	Dynamic Programming
133	Clone Graph	Medium	Depth-first Search Breadth-first Search Graph	DFS V.S. BFS
134	Gas Station	Medium	Greedy
135	Candy	Hard	Greedy
136	Single Number	Medium	Hash Table Bit Manipulation
137	Single Number II	Medium	Bit Manipulation
138	Copy List with Random Pointer	Hard	Hash Table Linked List
139	Word Break	Medium	Dynamic Programming
140	Word Break II	Hard	Dynamic Programming Backtracking
141	Linked List Cycle	Medium	Linked List Two Pointers
142	Linked List Cycle II	Medium	Linked List Two Pointers
143	Reorder List	Medium	Linked List
144	Binary Tree Preorder Traversal	Medium	Tree Stack
145	Binary Tree Postorder Traversal	Hard	Tree Stack
146	LRU Cache	Hard	Data Structure
147	Insertion Sort List	Medium	Linked List Sort
148	Sort List	Medium	Linked List Sort	! fast-slow to find middle + iterative reverse + merge sort
149	Max Points on a Line	Hard	Hash Table Math
150	Evaluate Reverse Polish Notation	Medium	Stack
151	Reverse Words in a String	Medium	String	README
152	Maximum Product Subarray	Medium	Array Dynamic Programming
153	Find Minimum in Rotated Sorted Array	Medium	Array Binary Search
154	Find Minimum in Rotated Sorted Array II	Hard	Array Binary Search
155	Min Stack	Easy	Stack Data Structure
157	Read N Characters Given Read4	Easy	String
158	Read N Characters Given Read4 II	Hard	String
160	Intersection of Two Linked Lists	Easy	Linked List	two pointers on two lists; combine long and short lists into one
161	One Edit Distance	Medium	String
162	Find Peak Element	Medium	Array Binary Search
163	Missing Ranges	Medium	Array
164	Maximum Gap	Hard	Sort
165	Compare Version Numbers	Easy	String
166	Fraction to Recurring Decimal	Medium	Hash Table Math
168	Excel Sheet Column Title	Easy	Math	convert decimal to other BASE system
169	Majority Element	Easy	Divide and Conquer Array Bit Manipulation
171	Excel Sheet Column Number	Easy	Math	convert other BASE system to decimal system
172	Factorial Trailing Zeroes	Easy	Math	count the number of certain number (e.g. 5) in n!
173	Binary Search Tree Iterator	Medium	Tree Stack
174	Dungeon Game	Hard	Dynamic Programming Binary Search
179	Largest Number	Medium	Sort
186	Reverse words in a string II	Medium	Array	two pass + include last position trick
187	Repeated DNA Sequences	Medium	Hash Table Bit Manipulation
188	Best Time to Buy and Sell Stock IV	Hard	Dynamic Programming
189	Rotate Array	Easy	Array
190	Reverse Bits	Easy	Bit Manipulation
191	Number of 1 Bits	Easy	Bit Manipulation
198	House Robber	Easy	Dynamic Programming
199	Binary Tree Right Side View	Medium	Tree Depth-first Search Breadth-first Search
200	Number of Islands	Medium	Depth-first Search Breadth-first Search
201	Bitwise AND of Numbers Range	Medium	Bit Manipulation
202	Happy Number	Easy	Hash Table Math
203	Remove Linked List Elements	Easy	Linked List
204	Count Primes	Easy	Hash Table Math	sieve algorithm
205	Isomorphic Strings	Easy	Hash Table
206	Reverse Linked List	Easy	Linked List
207	Course Schedule	Medium	Depth-first Search Breadth-first Search Graph Topological Sort
208	Implement Trie (Prefix Tree)	Medium	Data Structure Trie
209	Minimum Size Subarray Sum	Medium	Array Two Pointers Binary Search
210	Course Schedule II	Medium	Depth-first Search Breadth-first Search Graph Topological Sort
211	Add and Search Word - Data structure design	Medium	Backtracking Data Structure Trie
212	Word Search II	Hard	Backtracking Trie
213	House Robber II	Medium	Dynamic Programming
214	Shortest Palindrome	Hard	String
215	Kth Largest Element in an Array	Medium	Divide and Conquer Heap	max-heap using Java's Priority Queue
216	Combination Sum III	Medium	Array Backtracking
217	Contains Duplicate	Easy	Array Hash Table
218	The Skyline Problem	Hard	Divide and Conquer Heap
219	Contains Duplicate II	Easy	Array Hash Table
220	Contains Duplicate III	Medium	Binary Search Tree
221	Maximal Square	Medium	Dynamic Programming
222	Count Complete Tree Nodes	Medium	Tree Binary Search
223	Rectangle Area	Easy	Math
224	Basic Calculator	Medium	Stack Math
225	Implement Stack using Queues	Easy	Stack Data Structure
226	Invert Binary Tree	Easy	Tree
227	Basic Calculator II	Medium	String
228	Summary Ranges	Easy	Array
229	Majority Element II	Medium	Array	!vote algorithm
230	Kth Smallest Element in a BST	Medium	Tree Binary Search
231	Power of Two	Easy	Math Bit Manipulation
232	Implement Queue using Stacks	Easy	Stack Data Structure	README
233	Number of Digit One	Medium	Math
234	Palindrome Linked List	Easy	Linked List Two Pointers
235	Lowest Common Ancestor of a Binary Search Tree	Easy	Tree
236	Lowest Common Ancestor of a Binary Tree	Medium	Tree	README
237	Delete Node in a Linked List	Easy	Linked List
238	Product of Array Except Self	Medium	Array	O(N^2) -> two pass O(N)
239	Sliding Window Maximum	Hard	Heap	descending queue
240	Search a 2D Matrix II	Medium	Divide and Conquer Binary Search
241	Different Ways to Add Parentheses	Medium	Divide and Conquer
242	Valid Anagram	Easy	Hash Table Sort
246	Strobogrammatic Number	Easy	Hash Table Math
251	Flatten2DVector	Medium	Design
252	Meeting Rooms	Easy	Sort
253	Meeting Rooms II	Medium	Heap Greedy Sort
256	Paint House	Medium	Dynamic Programming
257	Binary Tree Paths	Easy	Tree
258	Add Digits	Easy	Math
260	Single Number III	Medium	Bit Manipulation
261	Graph Valid Tree	Medium	Breadth-first Search Depth-first Search Graph Union-Find
263	Ugly Number	Easy	Math
264	Ugly Number II	Medium	Math Heap
265	Paint House	Hard	Dynamic Programming
268	Missing Number	Medium	Array Math Bit Manipulation
269	Alien Dictionary	Hard	Graph Topological Sort	BFS
273	Integer to English Words	Medium	Math String
274	H-Index	Medium	Hash Table Sort
275	H-Index II	Medium	Binary Search
278	First Bad Version	Easy	Binary Search
279	Perfect Squares	Medium	Dynamic Programming Breadth-first Search Math
282	Expression Add Operators	Hard	Divide and Conquer
283	Move Zeroes	Easy	Array Two Pointers
284	Peeking Iterator	Medium	Design
285	Inorder Successor in BST	Medium	Tree
286	Walls And Gates	Medium	BFS
287	Find the Duplicate Number	Hard	Array Two Pointers Binary Search
289	Game of Life	Medium	Array
290	Word Pattern	Easy	Hash Table