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
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
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
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.
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)
136	Single Number	Python	1. Hash or set, O(n) and O(n) 2. xor 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)
151	Reverse Words in a String	Python	1. Python split by space 2. Reverse all and reverse words
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
186	Reverse Words in a String II ♥	Python	Reverse all and reverse each words
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.