Awesome
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.<br>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) <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 | Python 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 | Python Java | Background knowledge<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 | 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)<br>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 <br>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)<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 | Python | 1. Stack<br>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)<br>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 <br>2. KMP |
| 35 | Search Insert Position | Python | Binary Search |
| 46 | Permutations | Python | 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 | Permutations II | Python | 1. DFS with swapping, check duplicate, O(n^2) and O(n^2)<br>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)<br> 2. Bottom-up DP, O(n) and O(n)<br>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<br>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)<br>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 <br>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] <br>1. O(n) and O(n)<br>2. Only two variables are needed, O(n) and O(1) |
| 72 | Edit Distance | Python | Background<br> 1. DP O(n^2) space<br>2. DP O(n) space |
| 78 | Subsets | Python | 1. DFS Recursion, O(2^n) and O(2^n)<br>2. Recursion on a binary number, O(2^n) and O(2^n)<br>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)<br>2. Recursion on a binary number, O(2^n) and O(2^n)<br>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)<br>2. Stack and check isinstance(curr, TreeNode), O(n) and O(n)<br>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)<br>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)<br>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<br> 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)<br>2. xor O(n) and O(1) |
| 137 | Single Number II | Python | 1. ctypes 32 % 3 and &, O(n) and O(1)<br>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)<br>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<br> 2. Two points (fast and slow)<br>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)<br>2. Two points, O(n) and O(1) |
| 144 | Binary Tree Preorder Traversal | Python | 1. Recursion, O(n) and O(n)<br>2. Stack, O(n) and O(n) |
| 145 | Binary Tree Postorder Traversal | Python | 1. Recursion, O(n) and O(n)<br>2. Stack and queue (insert 0), O(n) and O(n)<br>3. Stack and isinstance(curr, TreeNode), O(n) and O(n) |
| 146 | LRU Cache | Python | 1. Queue and dict<br>2. OrderedDict |
| 150 | Evaluate Reverse Polish Notation | Python | Stack |
| 151 | Reverse Words in a String | Python | 1. Python split by space <br>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<br>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<br>2. sorted list, O(logn) for add, O(n) for find, O(n) space<br> 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)<br>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)<br>2. Traverse on prev and curr, then curr.next = prev, O(n) and O(1)<br>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 |
| 215 | Kth Largest Element in an Array | Python Java | 1. Sort, O(n) and O(n)<br>2. Heap, O(nlgk) and O(n)<br>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<br>2. Sort and check i,i +1 |
| 219 | Contains Duplicate II | Python | 1. Brute force<br> 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 <br>2. Bucket sort |
| 221 | Maximal Square | Python | 1. Brute force<br> 2. dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1, O(mn) and O(mn)<br>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)<br>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)<br>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)<br>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)<br>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)<br>2. XOR with index<br>3. Sort and binary search |
| 270 | Closest Binary Search Tree Value ♥ | Python | 1. Recursively brute force, O(n) and O(n)<br>2. Recursively compare root result with current kid's result (left or right), O(logn) and O(logn)<br>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<br>1. Sort and check number of papers greater than h, O(nlogn) and O(1)<br>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)<br>2. Sort and swap(i, i + 1) from 1 to n - 1, O(nlogn)<br>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!!)<br>2. Backtracking with memo, O(n!!) and O(n!)<br>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)<br>2. Tire tree, O(nk^2) and O(n) |
| 337 | House Robber III | Python | 1. Recursion with hash map, O(n) and O(n)<br>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). <br> 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)<br>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)<br>2. Recursively check level and return them, O(n) and O(n) |
| 367 | Valid Perfect Square | Python Java | Integer square root<br>1. 1+3+…+(2n-1) = n^2<br>2. Binary search<br>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)<br>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<br> 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<br>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<br>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<br>2. Condition check and string connect |
| 414 | Third Maximum Number | Python Java | 1. Keep max 1-3 then compare, O(n) and O(1)<br>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<br>2. Find segment in place |
| 437 | Path Sum III | Python Java | 1. Recursively travese the whole tree, O(n^2)<br>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)<br> 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)<br>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) <br>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.<br>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)<br>2. BFS, O(n^2) and O(1)<br>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)<br>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<br>2. Tree to string and compare |
| 581 | Shortest Unsorted Continuous Subarray | Python Java | 1. Sort and find the difference (min and max), O(nlgn)<br>2. Using stack to find boundaries (push when correct order, pop when not correct), O(n) and O(n)<br>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)<br>2. Sort, O(nlogn) and O(1)<br>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)<br>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)<br>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)<br>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)<br>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)<br>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)<br>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)<br>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:<br>1. str.lower() or str.toLowerCase()<br>2. ASCII processing. O(n) and O(1) |
| 716 | Max Stack ♥ | Python Java | 1. Two stacks<br> 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)<br>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)<br>2. Tire Tree, O(sum(w) and O(w))<br>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)<br>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)<br>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 <br> 2. Bin Mask, number of zeor equal to number of alpha<br>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)<br>2. Check area, O(1) and O(1) |
| 844 | Backspace String Compare | Python Java | 1. Stack pop when encounters #, O(n) and O(n)<br>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)<br>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)<br>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)<br>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)<br>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)<br>2. Scan all and split odd and even number into different array, O(n) and O(n)<br>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)<br>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)<br>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)<br>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)<br>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)<br>2. Min Heap, O(nlogk) and O(k) |
| 981 | Time Based Key-Value Store | Python | Get: O(log(n)) time<br>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)<br>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)<br>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)<br>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)<sup>2</sup>) |
| 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 |