Skip to content

Yiziwinnie/leetcode

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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 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)
2. 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)
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 Java Add another stack for min stack, maintance this stack when the main stack pop or push: 1. Only push min, such that len(minStack)<=len(Stack) 2. Push min again when current top is min, such that len(minStack)=len(Stack)
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)
216 Combination Sum III Python Generate all combinations of length k and keep those that sum to n
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)
273 Integer to English Words Python Java Careful about corner cases, such 1-20 and 21-Hundred, O(lgn) and O(1)
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
400 Nth Digit Python Java islands * 4 - overlaps * 2
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)
409 Longest Palindrome Python Java Length of Palindrome is always 2n or 2n + 1. So, get all possible 2*n, and choose a single one as 1 if it exists.
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)
434 Number of Segments in a String Python Java 1. trim &split
2. Find segment in place
437 Path Sum III Python Java 1. Recursively travese the whole tree, O(n^2)
2. Cache sum in Hash based on solution 1. Note that if sum(A->B)=target, then sum(root->a)-sum(root-b)=target.
438 Find All Anagrams in a String Python Java Build a char count list with 26-256 length. Note that this list can be update when going through the string. O(n) and O(1)
443 String Compression Python Java Maintain curr, read, write and anchor (start of this char).
448 Find All Numbers Disappeared in an Array Python Java Value (1, n) and index (0, n-1). Mark every value postion as negative. Then, the remain index with positive values are result. O(n)
453 Number of Segments in a String Python Java Each move is equal to minus one element in array, so the answer is the sum of all elements after minus min.
461 Hamming Distance Python Java Hamming Distance is related to XOR for numbers. So, XOR then count 1. O(n)
463 Island Perimeter Python Java math, find the area, actual number, then find the digit
482 License Key Formatting Python Java String processing, lower and len % K, O(n) and O(n)
538 Convert BST to Greater Tree Python Java Right first DFS with a variable recording sum of node.val and right.val. 1. Recursive.
2. Stack 3. Reverse Morris In-order Traversal
543 Diameter of Binary Tree Python Java DFS with O(1) for max answer
572 Subtree of Another Tree Python Java 1. Tree traverse and compare
2. Tree to string and compare
581 Shortest Unsorted Continuous Subarray Python Java 1. Sort and find the difference (min and max), O(nlgn)
2. Using stack to find boundaries (push when correct order, pop when not correct), O(n) and O(n)
3. Find min and max of unordered array, O(n) and O(1)
617 Merge Two Binary Trees Python Java Traverse both trees Recursion & Iterative (stack)
654 Maximum Binary Tree Python Java 1. Divide and conquer, recursive, O(n^2)
2. Monotonic stack, O(n)
709 To Lower Case Python Java String processing:
1. str.lower() or str.toLowerCase()
2. ASCII processing. O(n) and O(1)
716 Max Stack Python Java 1. Two stacks
2. Double linked list and Hash
771 Jewels and Stones Python Java Count given char in string. Hash or table. Oneline
804 Unique Morse Code Words Python Java String, Hash and Set. Set is recommended.
819 Most Common Word Python Java String processing, be careful about 'b,b,b'. regex is recommended.
904 Fruit Into Baskets Python Java 1. Scan through blocks of tree, O(n) and O(n)
2. Mainten a sliding window with start and curr point, O(n) and O(n).
929 Unique Email Addresses Python Java String handle and hash (or set)
945 Minimum Increment to Make Array Unique Python Java Sort, then list duplicate and missing value in sorted list. O(nlgn) and O(n)
946 Validate Stack Sequences Python Java Add a stack named inStack to help going through pushed and popped. O(n) and O(n)
# 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

About

My Python & JAVA Solutions for Leetcode

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 89.7%
  • Java 10.3%