Skip to content

Latest commit

 

History

History
262 lines (253 loc) · 78.6 KB

README.md

File metadata and controls

262 lines (253 loc) · 78.6 KB

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[0ls-2],dp[1ls-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.
523 Continuous Subarray Sum Python O(n) solution using dict()
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)2)
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
2429 Minimize XOR Python check the num1, num2 with length and replace "0" compare with num1.
# To Understand
4 Median of Two Sorted Arrays

Other LeetCode Repos

  1. LeetCode Algorithms ~anishLearnsToCode
  2. haoel's leetcode
  3. soulmachine's leetcode
  4. kamyu104's LeetCode
  5. gouthampradhan's leetcode