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.

#	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
11	Container With Most Water	Python Java	1. Brute Force, O(n^2) and O(1) 2. 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 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
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) 2. 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 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
179	Largest Number	Python Java	Define a comparator with str(x) + str(y) > str(y) + str(x), O(nlgn) and O(n)
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)
204	Count Primes	Python Java CPP	Sieve of Eratosthenes, O(nloglogn) and O(n)
206	Reverse Linked List	Python Java CPP	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)
207	Course Schedule	Python	Cycle detection problem
213	House Robber II	Python	f(k) = max(f(k – 2) + num[k], max(dp[0~~ls-2],dp[1~~ls-1], O(n) and O(1)
215	Kth Largest Element in an Array	Python Java	1. Sort, O(n) and O(n) 2. Heap, O(nlgk) and O(n) 3. Quick selection, O(klgn) and O(n)
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)
223	Rectangle Area	Python Java	Rectangle A + B - common area, O(1) and O(1)
228	Summary Ranges	Python	Detect start and jump, O(n) and O(1)
236	Lowest Common Ancestor of a Binary Tree	Python Java	1. Recursive check left, val and right, LCA is the split paths in tree, O(n) and O(n) 2. Store parents during traversing tree, reverse check their lowest common parent, O(n) and O(n)
238	Product of Array Except Self	Python Java	The ans is [0,i -1] * [i+1, len- 1]. We can twice for left and right (reverse), O(n) and O(n)
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)
253	Meeting Rooms II ♥	Python Java	1. Priority queue and sort, O(nlogn) and O(n) 2. Go through timeline. If it's a start then meeting + 1, else meeting - 1. The ans is the max(meeting) in timeline. 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)
336	Palindrome Pairs	Python Java	1. Create a reverse word to index map, then for each word, check prefix and posfix, O(nk^2) and O(n) 2. Tire tree, O(nk^2) 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)
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)
347	Top K Frequent Elements	Python Java	1. Sort by frequency, O(nlogn) and O(n). 2. we can build a min heaq (based on frequency), then pop min until there are k element, O(klgn) 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)
380	Insert, Delete, Get Random	Python	Uses both a list of nums and a list of their locations
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 Cpp	1. From 1 to n, condition check 2. Condition check and string connect
414	Third Maximum Number	Python Java	1. Keep max 1-3 then compare, O(n) and O(1) 2. PriorityQueue, O(n) and O(1)
415	Add Strings	Python Java	Two points, careful abour carry, O(n) and O(n)
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)
441	Arranging Coins	Python	O(n) time.
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.
458	Poor Pigs	Python Java	2 pigs for 5 * 5 metric
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
475	Heaters	Python Java	1. Binary search hourse in heater array, O(nlogn) and O(1) 2. Two points, O(nlogn) and O(1)
479	Largest Palindrome Product	Python Java	1. Product max palindrome than check, O(n^2) and O(1) 2. Math
482	License Key Formatting	Python Java	String processing, lower and len % K, O(n) and O(n)
485	Max Consecutive Ones	Python Java	Add one when encounter 1, set to 0 when encounter 0, O(n) and O(1)
509	Fibonacci Number	Python Java	1. Recursive, O(n) 2. DP with memo, O(n). Note that N<=30, which means that we can keep a memo from 0 to 30.
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
541	Reverse String II	Python Java	Handle each 2k until reaching end, On(n) and O(n)
543	Diameter of Binary Tree	Python Java	DFS with O(1) for max answer
547	Friend Circles	Python Java	1. DFS, O(n^2) and O(1) 2. BFS, O(n^2) and O(1) 3. Union-find, O(n^2) and O(n)
557	Reverse Words in a String III	Python Java	String handle: Split with space than reverse word, O(n) and O(n). Better solution is that reverse can be O(1) space in array.
560	Subarray Sum Equals K	Python Java	Note that there are n^2 possible pairs, so the key point is accelerate computation for sum and reduce unnecessary pair. 1. Cummulative sum, O(n^2) and O(1)/O(n) 2. Add sum into hash, check if sum - k is in hash, O(n) and O(n)
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)
605	Can Place Flowers	Python Java	One time scan, check [i-1] [i] and [i+1], O(n) and O(1)
617	Merge Two Binary Trees	Python Java	Traverse both trees Recursion & Iterative (stack)
628	Maximum Product of Three Numbers	Python Java	Actually, we should only care about min1, min2 and max1-max3, to find these five elements, we can use 1. Brute force, O(n^3) and O(1) 2. Sort, O(nlogn) and O(1) 3. Single scan with 5 elements keep, O(n) and O(1)
654	Maximum Binary Tree	Python Java	1. Divide and conquer, recursive, O(n^2) 2. Monotonic stack, O(n)
665	Non-decreasing Array	Python Java	1. Find the broken index, then check this point, O(n) and O(1) 2. Replace broken point with correct value, then check if there are more than 1 broken point, O(n) and O(1)
668	Kth Smallest Number in Multiplication Table	Python Java Cpp	Binary search, O(mlog(mn) and O(1)
671	Second Minimum Node In a Binary Tree	Python Java	Note that min value is root: 1. Get all values then find result, O(n) and O(n) 2. BFS or DFS traverse the tree, then find the reslut, O(n) and O(n)
674	Longest Continuous Increasing Subsequence	Python Java	Scan nums once, check nums[i] < nums[i+1], if not reset count, O(n) and O(1)
680	Valid Palindrome II	Python Java	Recursively check s[left == end, when not equal delete left or right.
692	Top K Frequent Words	Python Java	1. Sort based on frequency and alphabetical order, O(nlgn) and O(n) 2. Find top k with Heap, O(nlogk) and O(n)
695	Max Area of Island	Python Java	1. DFS, O(n^2) and O(n) 2. BFS, O(n^2) and O(n)
697	Degree of an Array	Python Java	1. Find degree and value, then find smallest subarray (start and end with this value), O(n) and O(n) 2. Go through nums, remember left most pos and right most for each value, O(n) and O(n)
700	Search in a Binary Search Tree	Python Java	Recursive or iteration, O(logn)
703	Kth Largest Element in a Stream	Python Java	1. Sort and insert into right place, O(nlgn) and O(n) 2. k largest heap, O(nlogk) and O(n)
706	Design HashMap	Python Java	Hash implementation, mod is fine. Be careful about key conflict and key remove.
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
717	1-bit and 2-bit Characters	Python Java	1. Go through bits, 1 skip next, O(n) and O(1) 2. Find second last zero reversely, O(n) and O(1)
720	Longest Word in Dictionary	Python Java	1. Brute Force, O(sum(w^2)) and O(w) 2. Tire Tree, O(sum(w) and O(w)) 3. Sort and word without last char, O(nlogn + sum(w)) and O(w)
724	Find Pivot Index	Python Java	Seach the array to find a place where left sum is equal to right sum, O(n) and O(1)
728	Self Dividing Numbers	Python Java	Brute Force check every digit, O(nlogD) and O(1)
733	Flood Fill	Python Java	1. DFS with stack or recursive, O(n) and O(n) 2. BFS with queue, O(n) and O(n)
743	Network Delay Time	Python Java	Let V == N, then: 1. DFS, O(V^V+ElgE), O(V+E) 2. Dijkstra, O(V^2+E), O(V+E)
751	IP to CIDR ♥	Python Java	Bit manipulations, incrementail is 1 << (32 - mask)
760	Find Anagram Mappings	Python Java	Hash table with A's (val, index), O(n) and O(n)
766	Toeplitz Matrix	Python Java	Check from top left to bottom right, i,j == i + 1, j + 1.
771	Jewels and Stones	Python Java	Count given char in string. Hash or table. Oneline
784	Letter Case Permutation	Python Java	Note that this is a 2^n problem. 1. Recursively generate result with previous result 2. Bin Mask, number of zeor equal to number of alpha 3. Python build in product.
804	Unique Morse Code Words	Python Java	String, Hash and Set. Set is recommended.
811	Subdomain Visit Count	Python Java	String split and HashMap, O(n) and O(n)
819	Most Common Word	Python Java	String processing, be careful about 'b,b,b'. regex is recommended.
832	Flipping an Image	Python Java	Invert and swap can be done at the same time, and careful about (n + 1)/2, O(n^2) and O(1)
836	Rectangle Overlap	Python Java	1. Check position, O(1) and O(1) 2. Check area, O(1) and O(1)
844	Backspace String Compare	Python Java	1. Stack pop when encounters #, O(n) and O(n) 2. Compare string from end to start, O(n) and O(1)
852	Peak Index in a Mountain Array	Python Java	1. Scan the array until encountering decline, O(n) and O(1) 2. Binary seach with additional check for [i + 1], O(logn) and O(1)
867	Transpose Matrix	Python Java	Res[i][j] = A[j][i]
868	Binary Gap	Python Java	1. Store index and check, O(logn) and O(logn) 2. One pass and store max, O(logn) and O(1)
872	Leaf-Similar Trees	Python Java	DFS (stack or recursion) get leaf value sequence and compare, O(n) and O(n)
876	Middle of the Linked List	Python Java	1. Copy to array, O(n) and O(n) 2. Fast and slow point, where fast point is 2 times faster than slow point, O(n) and O(1)
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).
905	Sort Array By Parity	Python Java	1. Sort with condition, O(nlogn) and O(1) 2. Scan all and split odd and even number into different array, O(n) and O(n) 3. In place swap similar to quick sort, O(n) and O(1)
922	Sort Array By Parity II	Python Java	1. Place odd and even number in odd and even place, not sort is needed. O(n) and O(1) 2. Two points with quick sort swap idea, O(n) and O(1).
929	Unique Email Addresses	Python Java	String handle and hash (or set)
933	Number of Recent Calls	Python Java	Queue, remove val in head when val < t - 3000, O(n) and O(n)
937	Reorder Log Files	Python Java	1. Comstom Sort, O(nlogn) and O(1) 2. Separete letter logs and digit logs, then sort letter logs and merge with digit logs, O(nlogn) and O(n)
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)
953	Verifying an Alien Dictionary	Python Java	Use hashmap to store index of each value, then create a comparator based on this index, O(n) and O(n)
954	Array of Doubled Pairs	Python Java	Sort, then use hashmap to store the frequency of each value. Then, check n, 2 * n in hashmap, O(nlogn) and O(n)
961	N-Repeated Element in Size 2N Array	Python Java	Hash and count number, O(n) and O(n)
962	Maximum Width Ramp	Python Java	1. Sort index by value, then transfer problem into finding max gap between index, O(nlogn) and O(1) 2. Binary Search for candicates, O(nlogn) and O(n)
977	Squares of a Sorted Array	Python Java	1. Sort, O(nlogn) and O(n) 2. Two point, O(n) and O(n)
973	K Closest Points to Origin	Python Java	1. Sort and get 0-K, O(nlogn) and O(1) 2. Min Heap, O(nlogk) and O(k)
981	Time Based Key-Value Store	Python	Get: O(log(n)) time Set: O(1) time
1064	Fixed Point ♥	Python Java	1. Go through index and value, until find solution encounter index < value, O(n) and O(1) 2. Binary search, O(logn) and O(1)
1089	Duplicate Zeros	Python Java	2 Pass, store last position and final move steps, O(n) and O(1)
1108	Defanging an IP Address	Python Java	String manipulate (split, replace and join), O(n) and O(n)
1189	Maximum Number of Balloons	Java	Count letters in `balon`, then find min, O(n) and O(1)
1260	Shift 2D Grid	Python Java	Final position of each element can be computed according to k, m and n, e.g., k == mn, then don't move, O(mn) and O(mn)
1290	Convert Binary Number in a Linked List to Integer	Python	Take 2 to the power digit position from right (starting from 0) and multiply it with the digit
1304	Find N Unique Integers Sum up to Zero	Python Java	[1,n-1] and its negative sum
1310	XOR Queries of a Subarray	Python Java Cpp	Compute accumulated xor from head, qeury result equals to xor[0, l] xor x[0, r], O(n) and O(n)
1323	Maximum 69 Number	Python Java	9 is greater than 6, so change first 6 to 9 from left if exist, O(n) and O(1)
1337	The K Weakest Rows in a Matrix	Python Java	Check by row, from left to right, until encount first zero, O(mn) and O(1)
1342	Number of Steps to Reduce a Number to Zero	Python	If number is divisible by 2, divide the number by 2, else subtract 1 from the number, and output the number of steps, O(logn) and O(1)
1365	How Many Numbers Are Smaller Than the Current Number	Python Java	1. Sort and get position in sorted nums, O(nlogn) and O(n) 2. Fill count into 0-100, O(n) and O(1)
1480	Running Sum of 1d Array	Python Java	1. Go through the array, O(n) and O(1) 2. Accumulate API
1539	Kth Missing Positive Number	Java	Binary search, num of missing = arr[i]-i-1
1909	Remove One Element to Make the Array Strictly Increasing	Python	Use brute-force. O( (nums.length)²)
1981	Minimize the Difference Between Target and Chosen Elements	Java	DP memo[row][sum] to avoid recomputing
2409	Count Days Spent Together	Python	Use month as a day
2413	Smallest Even Multiple	Python	Check the n is multiply by 2

#	To Understand
4	Median of Two Sorted Arrays

Other LeetCode Repos

License

indamutsa/leetcode-5

About

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages