ifahim / leetcode

My Python & JAVA Solutions for Leetcode

Python & JAVA Solutions for Leetcode (inspired by haoel's leetcode)

Remember solutions are only solutions to given problems. If you want full study checklist for code & whiteboard interview, please turn to jwasham's coding-interview-university.

Python and Java full list. ♥ means you need a subscription.

#	Title	Solution	Basic idea (One line)
1	Two Sum	Python Java	1. Hash O(n) and O(n) space. 2. Sort and search with two points O(n) and O(1) space.
2	Add Two Numbers	Python Java	Take care of the carry from lower digit.
3	Longest Substring Without Repeating Characters	Python Java	1. Check every possible substring O(n^2) 2. Remember the character index and current check pos, if character index >= current pos, then there is duplicate
4	Median of Two Sorted Arrays	Python Java	1. Merge two sorted lists and compute median, O(m + n) and O(m + n) 2. An extension of median of two sorted arrays of equal size problem
5	Longest Palindromic Substring	Python Java	Background knowledge 1. DP if s[i]==s[j] and P[i+1, j-1] then P[i,j] 2. A palindrome can be expanded from its center 3. Manacher algorithm
7	Reverse Integer	Python Java	Overflow when the result is greater than 2147483647 or less than -2147483648.
8	String to Integer (atoi)	Python Java	Overflow, Space, and negative number
9	Palindrome Number	Python Java	Get the len and check left and right with 10^len, 10
12	Integer to Roman	Python	Background knowledge Just like 10-digit number, divide and minus
13	Roman to Integer	Python	Add all curr, if curr > prev, then need to subtract 2 * prev
15	3Sum	Python	1. Sort and O(n^2) search with three points 2. Multiple Two Sum (Problem 1)
16	3Sum Closest	Python	Sort and Multiple Two Sum check abs
18	4Sum	Python	The same as 3Sum, but we can merge pairs with the same sum
20	Valid Parentheses	Python	1. Stack 2. Replace all parentheses with '', if empty then True
21	Merge Two Sorted Lists	Python	Add a dummy head, then merge two sorted list in O(m+n)
23	Merge k Sorted Lists	Python	1. Priority queue O(nk log k) 2. Binary merge O(nk log k)
24	Swap Nodes in Pairs	Python	Add a dummy and store the prev
28	Implement strStr()	Python	1. O(nm) comparison 2. KMP
35	Search Insert Position	Python	Binary Search
46	Permutations	Python	1. Python itertools.permutations 2. DFS with swapping, O(n^2) and O(n^2) 3. iteratively generate npermutations with n-1permutations, O(n^3) and O(n^2)
47	Permutations II	Python	1. DFS with swapping, check duplicate, O(n^2) and O(n^2) 2. iteratively generate npermutations with n-1permutations, O(n^3) and O(n^2)
53	Maximum Subarray	Python	1. Recursion, O(nlgn), O(lgn) 2. Bottom-up DP, O(n) and O(n) 3. Bottom-up DP, f(x) = max(f(x-1)+A[x], A[x]), f(x) = max(f(x-1)+A[x], A[x]),O(n) and O(1)
54	Spiral Matrix	Python	O(nm) 1. Turn in the corner and loop 2. (0, 1) -> (1, 0) -> (0, -1) -> (-1, 0)
62	Unique Paths	Python	1. Bottom-up DP, dp[i][j] = dmap[i-1][j] + dmap[i][j-1], O(mn) and O(mn) 2. Combination (m+n-2, m-1)
63	Unique Paths II	Python	Bottom-up DP, dp[i][j] = dmap[i-1][j] + dmap[i][j-1] (if block, then 0), O(mn) and O(mn)
65	Valid Number	Python	1. strip leading and tailing space, then check float using exception, check e using split 2. check is number split by . or e, note that number after e may be negative
66	Plus One	Python	Check if current digit == 9.
70	Climbing Stairs	Python	Bottom-up DP, dp[i] = dp[i - 2] + dp[i- 1] 1. O(n) and O(n) 2. Only two variables are needed, O(n) and O(1)
72	Edit Distance	Python	Background 1. DP O(n^2) space 2. DP O(n) space
78	Subsets	Python	1. DFS Recursion, O(2^n) and O(2^n) 2. Recursion on a binary number, O(2^n) and O(2^n) 3. Sort and iteratively generate n subset with n-1 subset, O(n^2) and O(2^n)
90	Subsets II	Python	1. DFS Recursion with duplicate check, O(2^n) and O(2^n) 2. Recursion on a binary number, O(2^n) and O(2^n) 3. Sort and iteratively generate n subset with n-1 subset, note that if nums[index] == nums[index - 1] then generate from last end to curr end, O(n^2) and O(2^n)
94	Binary Tree Inorder Traversal	Python	1. Recursion, O(n) and O(1) 2. Stack and check isinstance(curr, TreeNode), O(n) and O(n) 3. Stack and check left and right, O(n) and O(n)
98	Validate Binary Search Tree	Python	1. Stack O(n) and O(n) 2. Recursion O(n) and O(n)
104	Maximum Depth of Binary Tree	Python	Recursion max(left, right) + 1
108	Convert Sorted Array to Binary Search Tree	Python	Recursion O(n) and O(nlgn)
109	Convert Sorted List to Binary Search Tree	Python	1. Two points fast (next next) and slow (next) O(nlgn) and O(n) 2. Bottom-up recursion O(n) and O(lgn)
110	Balanced Binary Tree	Python	Recursion 1. Top-down O(n^2) and O(n), Bottom-up recursion with sentinel -1 O(n) and O(n)
111	Minimum Depth of Binary Tree	Python	1. Recursion, note that when size of left (ld) or right (rd) is 0, then min = 1 + ld + rd 2. BFS check by level (right most), which is much faster than recursion
124	Binary Tree Maximum Path Sum	Python	Recursion O(n) and O(n), max (left + node, right + node, left + node + right)
125	Valid Palindrome	Python	Exclude non-alphanumeric characters and compare O(n)
128	Longest Consecutive Sequence	Python	Set or hash, pop adjacency, O(n) and O(n)
133	Clone Graph	Python	Hash and DFS or BFS
136	Single Number	Python	1. Hash or set, O(n) and O(n) 2. xor O(n) and O(1)
137	Single Number II	Python	1. ctypes 32 % 3 and &, O(n) and O(1) 2. ones, twos, threes as bitmask (e.g. ones represents ith bit had appeared once), O(n) and O(1)
138	Copy List with Random Pointer	Python	1. Hash O(n) and O(n) 2. Modify original structure: Original->Copy->Original, then node.next.random = node.random.next, O(n) and O(1)
141	Linked List Cycle	Python	1. Hash or set 2. Two points (fast and slow) 3. Add a max and check if reach the max
142	Linked List Cycle II	Python	Two points, a+b=nr
143	Reorder List	Python	1. List as index to rebuild relation, O(n) and O(n) 2. Two points, O(n) and O(1)
144	Binary Tree Preorder Traversal	Python	1. Recursion, O(n) and O(n) 2. Stack, O(n) and O(n)
145	Binary Tree Postorder Traversal	Python	1. Recursion, O(n) and O(n) 2. Stack and queue (insert 0), O(n) and O(n) 3. Stack and isinstance(curr, TreeNode), O(n) and O(n)
146	LRU Cache	Python	1. Queue and dict 2. OrderedDict
150	Evaluate Reverse Polish Notation	Python	Stack
151	Reverse Words in a String	Python	1. Python split by space 2. Reverse all and reverse words
152	Maximum Product Subarray	Python	DP, f(k) = max(f(k-1) * A[k], A[k], g(k-1) * A[k]), g(k) = min(g(k-1) * A[k], A[k], f(k-1) * A[k]), O(n) and O(1)
153	Find Minimum in Rotated Sorted Array	Python	Binary search with conditions, A[l] > A[r]
154	Find Minimum in Rotated Sorted Array II	Python	Binary search with conditions, A[l] > A[r], A[l]=A[mid]=A[r]
155	Min Stack	Python	Add another stack for min stack, maintance this stack when the main stack pop or push
156	Binary Tree Upside Down ♥	Python	p.left = parent.right, parent.right = p.right, p.right = parent, parent = p.left, p = left
157	Read N Characters Given Read4 ♥	Python	Handle the edge case (the end)
158	Read N Characters Given Read4 II - Call multiple times ♥	Python	Store the pos and offset that is read by last read4
159	Longest Substring with At Most Two Distinct Characters ♥	Python	Maintain a sliding window that always satisfies such condition
161	One Edit Distance ♥	Python	1. Check the different position and conditions 2. Edit distance
163	Missing Ranges ♥	Python	Add -1 to lower for special case, then check if curr - prev >= 2
166	Fraction to Recurring Decimal	Python	% and Hash to find duplicate
167	Two Sum II - Input array is sorted	Python	Two points O(n) and O(1)
170	Two Sum III - Data structure design ♥	Python	1. Hash, O(1) for add, O(n) for find, O(n) space 2. sorted list, O(logn) for add, O(n) for find, O(n) space 3. Sort before find, O(1) for add, O(nlogn) for find, O(n) space
186	Reverse Words in a String II ♥	Python	Reverse all and reverse each words
198	House Robber	Python	f(k) = max(f(k – 2) + num[k], f(k – 1)), O(n) and O(1)
200	Number of Islands	Python	1. Quick union find, O(nlogn) and O(n^2) 2. BFS with marks, O(n^2) and O(1)
206	Reverse Linked List	Python	1. Stack, O(n) and O(n) 2. Traverse on prev and curr, then curr.next = prev, O(n) and O(1) 3. Recursion, O(n) and O(1)
213	House Robber II	Python	f(k) = max(f(k – 2) + num[k], max(dp[0ls-2],dp[1ls-1], O(n) and O(1)
217	Contains Duplicate	Python	1. Set and compare length 2. Sort and check i,i +1
219	Contains Duplicate II	Python	1. Brute force 2. Maintenance a set that contains previous k numbers, and check if curr in set
220	Contains Duplicate III	Python	1. Sort and binary Search 2. Bucket sort
221	Maximal Square	Python	1. Brute force 2. dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1, O(mn) and O(mn) 3. dp[j] = min([j], dp[j-1], prev) + 1, O(mn) and O(n)
228	Summary Ranges	Python	Detect start and jump, O(n) and O(1)
243	Shortest Word Distance	Python	Update index1 and index2, and check distance, O(n) and O(1)
246	Strobogrammatic Number ♥	Python	Hash table and reverse string, O(n) and O(n)
249	Group Shifted Strings ♥	Python	Hash and generate hash code for each string, O(n) and O(n)
252	Meeting Rooms	Python	1. Sort and compare intervals[i].end with intervals[i+1], O(nlogn) and O(1) 2. Sort and check intervals when count >= 2, O(nlogn) and O(n)
259	3Sum Smaller	Python	1. Reduce to two sum smaller, then binary search, O(n^2lgn) and O(1) 2. Reduce to two sum smaller, then two points, O(n^2) and O(1)
266	Palindrome Permutation ♥	Python	Compute frequency, check number of odd occurrences <= 1 then palindrome, O(n) and O(n)
267	Palindrome Permutation II ♥	Python	Check palindrome then generate half with Permutations II, O(n^2) and O(n^2)
268	Missing Number	Python Java	1. Find missing by n * (n - 1)/2 - sum(nums) 2. XOR with index 3. Sort and binary search
270	Closest Binary Search Tree Value ♥	Python	1. Recursively brute force, O(n) and O(n) 2. Recursively compare root result with current kid's result (left or right), O(logn) and O(logn) 3. Iteratively compare root result with current kid's result (left or right), O(logn) and O(logn)
274	H-Index	Python	Background 1. Sort and check number of papers greater than h, O(nlogn) and O(1) 2. Counting sort, O(n) and O(n)
276	Paint Fence ♥	Python	ways[i>2] = (ways[i-1] + ways[i-2]) * (k - 1), O(n) and O(1)
280	Wiggle Sort ♥	Python	1. Sort and insert (n - 1) / 2 from tail to correct position, O(nlogn) and O(1) 2. Sort and swap(i, i + 1) from 1 to n - 1, O(nlogn) 3. Iteratively check order and reverse order, if not satisfied, then swap i with i + 1, O(n)
286	Walls and Gates	Python	BFS with queue, O(mn) and O(mn)
288	Unique Word Abbreviation ♥	Python	hash
293	Flip Game ♥	Python	Python string slicing
294	Flip Game II ♥	Python	1. Backtracking to ensure that next step is False, O(n!!) and O(n!!) 2. Backtracking with memo, O(n!!) and O(n!) 3. DP based on Sprague-Grundy Function
296	Best Meeting Point ♥	Python	Think hard about Manhattan Distance in 1D case. Sort and find mean, O(mnlogmn) and O(1)
298	Binary Tree Longest Consecutive Sequence ♥	Python	Bottom-up or top-down recursion, O(n) and O(n)
305	Number of Islands II	Python	Quick union find with weights, O(nlogn) and O(n)
322	Coin Change	Python	Bottom-up or top-down DP, dp[n] = min(dp[n], dp[n - v_i]), where v_i is the coin, O(amount * n) and O(amount)
337	House Robber III	Python	1. Recursion with hash map, O(n) and O(n) 2. Recursion on two steps, O(n) and O(1)
339	Nested List Weight Sum ♥	Python	Depth-first recursion
340	Longest Substring with At Most K Distinct Characters ♥	Python	Maintain a sliding window with at most k distinct characters and a count for this window. Note that the start position need a loop to update.
346	Moving Average from Data Stream ♥	Python	fix-sized queue or dequeue, O(1) and O(n)
351	Android Unlock Patterns ♥	Python	Backtracking, O(n!) and O(n)
359	Logger Rate Limiter ♥	Python	1. hash which stores the latest timestamp, O(1) and O(n) 2. Using Priority queue to remove older logs, O(n) and O(n)
366	Find Leaves of Binary Tree ♥	Python	1. Set or hash to check leaft, O(n^2) and O(n) 2. Recursively check level and return them, O(n) and O(n)
367	Valid Perfect Square	Python Java	Integer square root 1. 1+3+…+(2n-1) = n^2 2. Binary search 3. Newton's method
368	Largest Divisible Subset	Python	Sort and generate x subset with previous results, O(n^2) and O(n^2)
369	Plus One Linked List ♥	Python	1. Stack or list that store the list, O(n) and O(n) 2. Two points, the first to the tail, the second to the latest place that is not 9, O(n) and O(1)
370	Range Addition ♥	Python	Interval problem with cumulative sums, O(n + k) and O(n)
383	Ransom Note	Python Java	Get letter frequency (table or hash map) of magazine, then check randomNote frequency
384	Shuffle an Array	Python	Fisher–Yates shuffle, O(n) and O(n)
387	First Unique Character in a String	Python Java	Get frequency of each letter, return first letter with frequency 1, O(n) and O(1)
388	Longest Absolute File Path	Python	Store last length and rindex, O(n) and O(n)
389	Find the Difference	Python Java	1. Imaging letter a as 0, then the sum(t)-sum(s) is the result 2. Based on solution 1, bit manipulate
401	Binary Watch	Python Java	Note that 12 * 60 is much less than 2^n or n^2.
404	Sum of Left Leaves	Python Java	1. Recursively DFS with root.left.left and root.left.right check 2. The same DFS based on stack
405	Convert a Number to Hexadecimal	Python Java	Two's complement 1. Bit manipulate, each time handle 4 digits 2. Python (hex) and Java API (toHexString & Integer.toHexString)
408	Valid Word Abbreviation ♥	Python	Go over abbr and word, O(n) and O(1)
412	Fizz Buzz	Python Java	1. From 1 to n, condition check 2. Condition check and string connect
416	Partition Equal Subset Sum	Python	DP, Check if sum of some elements can be half of total sum, O(total_sum / 2 * n) and O(total_sum / 2)
421	Maximum XOR of Two Numbers in an Array	Python	Check 0~32 prefix, check if there is x y in prefixes, where x ^ y = answer ^ 1, O(32n) and O(n)
422	Valid Word Square ♥	Python	Compare row with column, O(n^2)

#	To Understand
4	Median of Two Sorted Arrays

Other Leetcode Repos

1. haoel's leetcode
2. soulmachine's leetcode
3. kamyu104's LeetCode
4. gouthampradhan's leetcode