Python & JAVA Solutions for Leetcode.zip

# Python & JAVA Solutions for Leetcode (inspired by [haoel's leetcode](https://github.com/haoel/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](https://github.com/jwasham/coding-interview-university). Also, there are open source implementations for basic data structs and algorithms, such as [Algorithms in Python](https://github.com/TheAlgorithms/Python) and [Algorithms in Java](https://github.com/TheAlgorithms/Java). I'm currently working on [Analytics-Zoo](https://github.com/intel-analytics/analytics-zoo) - an unified Data Analytics and AI platform. Check it out, if you are interested in big data and deep learning. ## Problems & Solutions [Python](https://github.com/qiyuangong/leetcode/tree/master/python) and [Java](https://github.com/qiyuangong/leetcode/tree/master/java) full list. &hearts; means you need a subscription. | # | Title | Solution | Basic idea (One line) | |---| ----- | -------- | --------------------- | | 1 | [Two Sum](https://leetcode.com/problems/two-sum/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/001_Two_Sum.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/001_Two_Sum.java) | 1. Hash O(n) and O(n) space.<br>2. Sort and search with two points O(n) and O(1) space. | | 2 | [Add Two Numbers](https://leetcode.com/problems/add-two-numbers/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/002_Add_Two_Numbers.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/002_Add_Two_Numbers.java) | Take care of the carry from lower digit. | | 3 | [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/003_Longest_Substring_Without_Repeating_Characters.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/003_Longest_Substring_Without_Repeating_Characters.java) |1. Check every possible substring O(n^2) <br>2. Remember the character index and current check pos, if character index >= current pos, then there is duplicate | | 4 | [Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/004_Median_of_Two_Sorted_Arrays.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/004_Median_of_Two_Sorted_Arrays.java) | 1. Merge two sorted lists and compute median, O(m + n) and O(m + n)<br>2. An extension of median of two sorted arrays of equal size problem| | 5 | [Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/005_Longest_Palindromic_Substring.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/005_Longest_Palindromic_Substring.java) | [Background knowledge](http://en.wikipedia.org/wiki/Longest_palindromic_substring)<br>1. DP if s[i]==s[j] and P[i+1, j-1] then P[i,j]<br>2. A palindrome can be expanded from its center<br>3. Manacher algorithm| | 7 | [Reverse Integer](https://leetcode.com/problems/reverse-integer/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/007_Reverse_Integer.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/007_Reverse_Integer.java) | Overflow when the result is greater than 2147483647 or less than -2147483648. | 8 | [String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/008_String_to_Integer(atoi).py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/008_String_to_Integer(atoi).java) | Overflow, Space, and negative number | | 9 | [Palindrome Number](https://leetcode.com/problems/palindrome-number/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/009_Palindrome_Number.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/009_Palindrome_Number.java) | Get the len and check left and right with 10^len, 10 | | 11 | [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/011_Container_With_Most_Water.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/011_Container_With_Most_Water.java) | 1. Brute Force, O(n^2) and O(1)<br>2. Two points, O(n) and O(1) | | 12 | [Integer to Roman](https://leetcode.com/problems/integer-to-roman/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/012_Integer_to_Roman.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/012_Integer_to_Roman.java) | [Background knowledge](http://www.rapidtables.com/convert/number/how-number-to-roman-numerals.htm) Just like 10-digit number, divide and minus | | 13 | [Roman to Integer](https://leetcode.com/problems/roman-to-integer/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/013_Roman_to_Integer.py) | Add all curr, if curr > prev, then need to subtract 2 * prev | | 15 | [3Sum](https://leetcode.com/problems/3sum/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/015_3Sum.py) | 1. Sort and O(n^2) search with three points <br>2. Multiple Two Sum (Problem 1) | | 16 | [3Sum Closest](https://leetcode.com/problems/3sum-closest/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/016_3Sum_Closest.py) | Sort and Multiple Two Sum check abs| | 18 | [4Sum](https://leetcode.com/problems/4sum/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/018_4Sum.py) | The same as 3Sum, but we can merge pairs with the same sum | | 19 | [Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/019_Remove_Nth_Node_From_End_of_List.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/019_Remove_Nth_Node_From_End_of_List.java) | 1. Go through list and get length, then remove length-n, O(n) and O(n)<br>2. Two pointers, first pointer goes to n position, then move both pointers until reach tail, O(n) and O(n) | | 20 | [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/020_Valid_Parentheses.py) | 1. Stack<br>2. Replace all parentheses with '', if empty then True | | 21 | [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/021_Merge_Two_Sorted_Lists.py) | Add a dummy head, then merge two sorted list in O(m+n) | | 23 | [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/023_Merge_k_Sorted_Lists.py) | 1. Priority queue O(nk log k)<br>2. Binary merge O(nk log k)| | | 24 | [Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/024_Swap_Nodes_in_Pairs.py) | Add a dummy and store the prev | | 28 | [Implement strStr()](https://leetcode.com/problems/implement-strstr/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/028_Implement_strStr().py) | 1. O(nm) comparison <br>2. KMP | | 35 | [Search Insert Position](https://leetcode.com/problems/search-insert-position/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/035_Search_Insert_Position.py) | Binary Search | | 46 | [Permutations](https://leetcode.com/problems/permutations/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/046_Permutations.py) | 1. Python itertools.permutations<br>2. DFS with swapping, O(n^2) and O(n^2)<br>3. iteratively generate n-permutations with (n-1)-permutations, O(n^3) and O(n^2) | | 47 | [Permut