My Python Solutions for Leetcode

The whole lists:

♥ means you need a subscription.

#	Title	Solution	Basic idea (One line)
1	Two Sum	Python	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	Note the carry from lower digit.
3	Longest Substring Without Repeating Characters	Python	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
5	Longest Palindromic Substring	Python	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	Overflow when the result is greater than 2147483647
8	String to Integer (atoi)	Python	Overflow, Space, and negative number
9	Palindrome Number	Python	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
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
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](https://github.com/qiyuangong/leetcode/blob/master/python/124. Binary Tree Maximum Path Sum.py)	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, 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)
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)
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)
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)
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)
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.