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.

Also, there are open source implementations for basic data structs and algorithms, such as Algorithms in Python and Algorithms in Java.

I'm currently working on 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 and Java full list. ♥ means you need a subscription.

1. 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)

3. An extension of median of two sorted arrays of equal size problem| | 5 | Longest Palindromic Substring | Python Java | Background knowledge

4. DP if s[i]==s[j] and P[i+1, j-1] then P[i,j]

5. A palindrome can be expanded from its center

6. 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 | | 11 | Container With Most Water | Python Java | 1. Brute Force, O(n^2) and O(1)

7. Two points, O(n) and O(1) | | 12 | Integer to Roman | Python Java | 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

8. 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 | | 19 | Remove Nth Node From End of List | Python Java | 1. Go through list and get length, then remove length-n, O(n) and O(n)

9. Two pointers, first pointer goes to n position, then move both pointers until reach tail, O(n) and O(n) | | 20 | Valid Parentheses | Python | 1. Stack

10. 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)

11. 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

12. KMP | | 35 | Search Insert Position | Python | Binary Search | | 46 | Permutations | Python | 1. Python itertools.permutations

13. DFS with swapping, O(n^2) and O(n^2)

14. iteratively generate n-permutations with (n-1)-permutations, O(n^3) and O(n^2) | | 47 | Permutations II | Python | 1. DFS with swapping, check duplicate, O(n^2) and O(n^2)

15. iteratively generate n-permutations with (n-1)-permutations, O(n^3) and O(n^2) | | 53 | Maximum Subarray | Python | 1. Recursion, O(nlgn), O(lgn)

16. Bottom-up DP, O(n) and O(n)

17. 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

18. (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)

19. 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

20. 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]

21. O(n) and O(n)

22. Only two variables are needed, O(n) and O(1) | | 72 | Edit Distance | Python | Background

23. DP O(n^2) space

24. DP O(n) space | | 78 | Subsets | Python | 1. DFS Recursion, O(2^n) and O(2^n)

25. Recursion on a binary number, O(2^n) and O(2^n)

26. 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)

27. Recursion on a binary number, O(2^n) and O(2^n)

28. 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)

29. Stack and check isinstance(curr, TreeNode), O(n) and O(n)

30. Stack and check left and right, O(n) and O(n) | | 98 | Validate Binary Search Tree | Python | 1. Stack O(n) and O(n)

31. 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)

32. 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

33. 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](https://github.com/qiyuangon