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