Reminding myself that all it takes is practice, dedication and hard work. I put this off for too many years
24/12
- [x] 760 Find Anagram Mappings (redid 11/01 improved)
- [x] [ ] 1266 Minimum Time Visiting All Points Solution to study (redid 11/01 - no improvement)
- [x] 1221 Split a String in Balanced Strings (redid 11/01 improved!!) (redo again)
- [x] 1119 Remove Vowels from a String (redid 11/01 and improved)
- [x] 1295 Find Nu mbers with Even Number of Digits (redid 11/01 and improved)
- [x] 71 Jewels and Stones (redid 11/01 and improved)
- [x] 1290 Convert Binary Number in a Linked List to Integer (redid 11/01 and improved) (however, try bitwise next time)
- [x] 938 Range Sum of BST Youtube Video Explanation (getting better ... but redo again)
25/12
- [x] 1252 Cells With Odd Values in a Matrix [https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/discuss/456746/python3-simple-and-memory-saving-solution] (redid 11/01 - improved) (learn that solution ^ but came up with my own one too)
30/12
- [x] 1134 Armstrong Number Solution to study and Good solution demonstrating use of list comprehensions (improved 11/01)
- [x] 1213 Intersection of Two Arrays (redid 11/01 - improved) [try this again with a PQ]
03/01
- Think Like a Programmer (V. Anton Spraul) Recursion Problems
- [x] 1086 High Five (improved 11/01 but didn't used the optimal data structure)
- [x] 1299 Replace Elements with Greatest Element on Right Side
- [x] 344 Reverse String (easy problem to learn to optimise)
- [x] 136 Single Number (study XOR bitwise operators and how it works)
05/01
- [ ] 412 FizzBuzz
- [ ] 104 Max Depth of Binary Tree
- [x] 206 Reverse Linked List (important - learned recursive implementation)
- [ ] 237 Delete Node in a Linked List
- [ ] 203 Move Zeroes Solution to Study and study this method too: Link
- [ ] 169 Majority Element Solution to Study
- [ ] 242 Valid Anagram Solution to Study
- [x] 217 Contains Duplicate
06/01
- [ ] Convert Sorted Array to BST (Redo this everyday until I finally understand it)
- [x] Roman to Integer
- [ ] Best Time to Buy and Sell Stock II
07/01
- [ ] 171 Excel Sheet Column Number (redo and study all the solutions)
- [x] 387 First Unique Character in a String (yayyyy)
08/01
- [ ] 371 Sum of Two Integers (redo this and understand the Python error handling)
11/01
- Redid all problems from 24/12
- Redid all problems from 25/12
- Redid all problems from 30/12
- [x] 1 Two Sum (remember how to optimise this) (redid 12/01)
- 125 Valid Palindrome (note that in this version, if there is a space or non-alphanumeric character, you simply ignore it)
- 21 Merge Two Sorted Lists (redo this one) (try and write this recursively and study it) [https://leetcode.com/problems/merge-two-sorted-lists/discuss/472279/Python-Recursive-Solution]
12/01
- [ ] 1099 Two Sum Less Than K
- [ ] 350 Intersection of Two Arrays II
- Redid Two Sum
- Redid 206 Reverse Linked List
- Two Sum II - Input Array is Sorted (redo this with binary search!)
- 20 Valid Parentheses
13/01 Linked Lists + Arrays
- Redo Reversed Linked List
- Linked List Cycle (redo this one!)
- 53 Maximum Subarray
14/01 Trees
- 543 Diameter of Binary Tree
- 706 Design HashMap
- 1304 Find N Unique Integers Sum Up to Zero
- 1137 Nth Tribonacci Number
18/01
- Find N Unique Integers Sum up to Zero
- 1002 Find Common Characters
- 832 Flipping an Image
19/01
- 448 Find All Numbers Disappears in an Array
- 557 Reverse Words in a String III
- 905 Sort Array by Parity
- 286 Missing Number
- 234 Palindrome Linked List
- Redid reverse linked list (learn the iterative version)
- 203 Remove Linked List Elements
- 160 Intersection of Two Linked Lists
21/01
- redid 1299 Replace Elements with Greatest Element on Right Side
- redid 344 Reverse String
- redid 217 Contains Duplicates
- redid Roman to Integer
- redid First Unique Char
22/01 Stacks!
- [x] Remove Outermost Parenthesis
- 1047 Remove Duplicates
- 682 Baseball Game (failed this)
27/01
- Redid Remove Outermost Parenthesis
- Redid 1047 Remove All Adjacent duplicates
- 155 Min Stack (redo this one)
- 844 Backspace String Compare (look at two pointer solution for this)
- 232 Implement a Queue using a Stack (https://www.youtube.com/watch?v=Wg8IiY1LbII)
29/01 (hash tables, strings and arrays) Below are all the dynamic programming questions marked easy
- 690 Employee Importance
- 389 Find the Difference
- 500 Keyboard Row
- 99 Minimum Index Sum of Two Lists?
- 1207 Unique Number of Occurrences
- [x] 202 Happy Number (redo this one because common!)
30/01 (start doing recursion and dynamic programming problems from Google)
- 1025 Divisor Game
- 256 Paint House
- 121 Best Time to Buy and Sell Stock
- 746 Min Cost Climbing Stairs
- 392 Is Subsequence
- 70 Climbing Stairs
- 53 Maximum Subarray
- 198 House Robber
- Range Sum Query - Immutable
- 276 Paint Fence
31/01 (must try these ones)
- 255 Implement a Stack using Queues
- 496 Next Greater Element
- 852 Peak Index in a Mountain Array ?
- 704 Binary Search (implementing binary search)
- 69 Sqrt(x)
01/02
- Distribute Candies
- Redid Happy Number
- 953 Verifying an Alien Dictionary
- 409 Longest Palindrome
- 299 Bulls and Cows
02/02
- Redid Single Number
- Redid Reverse a String
- Redid Move Zeroes
- Redid Majority Element
- Redid Valid Anagram
- Redid Longest Palindrome
- Redid Verifying an Alien Dictionary
- 204 Count Primes (try to understand this ?? )
03/03
- Redo Excel Column Sheet Number
- Completed ctci 4.2 (took a long time to understand)
- Attempted ctci 4.3 (https://www.youtube.com/watch?v=iFkCxbn-9gY)
04/03
- Redid Two Sum **
- 15 3Sum
- Redo First Unique Char **
- 219 Contains Duplicate II
- 739 Daily Temperatures
- 692 Top K Frequent Words
- 17 Letter Combinations of a Phone Number
05/03 InterviewCake
08/02 InterviewCake Greedy Problems
- 153 Find Minimum in Rotated Sorted Array
10/02 (redo these ones to see if I actually understood them)
- 463 Island Perimeter (redo this one)
- 111 Minimum Depth of Binary Tree
- 226 Invert Binary Tree
- 972 Leaf-Similar Trees (don't understand this one below?)
- 589 N-ary Tree Preorder Traversal
11/02 (still learning how to do graphs properly)
- InterviewCake Graph Section
13/02 and 15/02 Haven't been keeping track since I've been doing InterviewCake but doing recursion and backtracking at the moment as of 16/02.
- 46 Permutations
- 1180 Count Substrings with Only One Distinct Letter (redo this)
- 576 Permutation in String (redo this and optimise)
- Learned the sliding window! (https://www.youtube.com/watch?v=MK-NZ4hN7rs)
26/02
- 39 Combination Sum (learn how to handle duplicates and redo this)
27/02 Probably go start to DP and hash tables and trees Attempt all the EASY tree questions [ ] Combination Sum II (do the variations of combination sum!) [x] 155 Min Stack (redid this) [x] 20 Valid Parentheses (redid this) [x] 498 Next Greater Element (still attempting this) [redo this and ty to do as many stack problems as I can] [ ] N-ary Tree Preorder Traversal [ ] N-ary Tree Postorder Traversal [ ] Univalued Binary Tree [ ] Leaf Similar Trees [ ] 100 Same Tree
28/02 Do stacks! [x] 706 Design HashMap (try redoing this with a linked list) [x] Daily Temperature [x] 40 Combination Sum II [x] 118 Pascal's Triangle
01/03 [x] 921 Minimum Add to Make Parentheses Valid [x] 347 Top K Frequent Elements (redo this) [x] 49 Group Anagrams (redo this) [ ] 36 Valid Sudoku (redo this - not working!)
02/03 Do some queues, graphs amd try starting dp [ ] 216 Combination Sum III [ ] 609 Find Duplicate File in System [ ] 341 Flattened Nested List Iterator [ ] 53 Maximum Subarray [ ] 1120 Maximum Average Subtree [ ] 547 Friend Circles [ ] Merge Two Binary Trees [ ] 215 Kth Largest Element in an Array
Good string questions to attempt:
- 38 Count and Say
- 415 Add Strings
- 14 Longest Common Prefix
- 788 Rotated Digits
Med
- 6 ZigZag Conversion
- 3 Longest Substring Without Repeating Characters
- Longest Palindromic String
- Longest Common Prefix
- 12 Integer to Roman
- 22 Generate Parentheses
- 38 Count and Say
- Add Binary
- Group Anagrams
- 151 Reverse Words in a String
Good hash table questions to attempt:
- 463 Island Perimeter
- 219 Contains Duplicate II
- 3 Longest Substring Without Repeating Characters
Good tree questions to attempt:
- 94 Binary Tree Inorder Traversal
- 101 Symmetric Tree
- 111 Minimum Depth of Binary Tree
- Lowest Common Ancestor Binary Tree
12/01
- 2 Add Two Numbers
- 3 Longest Substring Without Repeating Characters
- 5 Longest Palindromic Substring
** If I have this, [[2, 3, 3], [2, 2, 2, 2], [3, 2, 3], [3, 5], [3, 3, 2], [5, 3]], know how to write a function that removes the duplicates and only gets lists that are unique
- Radix Sort
- Counting Sort
- Heap Sort
- Topological sort
- Determine if a string is an int or a double
- Find the shortest palidrome in a string
- Print all permutations of a string
- Find the only element in an array that occurs once (did this multiple times but keep forgetting) (remember bitwise operators always undo each other if they match)
- Permutations
- Backtracking
- Permutations and palindromes
- Iterators in Python
- Graphs
Permutation
You are given a 7 digit phone number, and you should find all possible letter combinations based on the digit-to-letter mapping on numeric pad and return only the ones that have valid match against a given dictionary of words. Give all possible letter combinations from a phone number. Generate all subsets of a string. Print all possible N pairs of balanced parentheses. E.g. when N is 2, the function should print (()) and ()(). E.g. when N is 3, we should get ((())), (()()), (())(), ()(()), ()()(). Source Given a list of arrays, return a list of arrays, where each array is a combination of one element in each given array. E.g. If the input is [[1, 2, 3], [4], [5, 6]], the output should be [[1, 4, 5], [1, 4, 6], [2, 4, 5], [2, 4, 6], [3, 4, 5], [3, 4, 6]].
- Use % 10 to get the last digit
- Use // 10 to get the whole number without the last digit
- For the two above points, loop it until != 0 (this is the base case)
- *=2 is same as <<=1 (revise this)
- Use list comprehension with joins
- Use multiple pinters
- Useful to use enumerate function in Python
- Head recursion is where the recursive call comes BEFORE other processing in the function (recursive call happens before the other processing)
- Tail recursion is where the processing occurs BEFORE the recursive call - recursive call is the last step in the function (recursive call is postponed until the end)
- If you set("aabc"), you get {a, b, c} (useful in finding distinct characters) [https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/]
- Use the functions for dictionarys i.e. .keys() returns the keys in an object e.g.
for i in dictionary.keys():
print(i)
- Use .get() to get the value of the respective key you are getting
- Make use of being able to traverse Python backwards easily e.g. (len(aList) - 1, -1, -1)
- Make use of XOR and reduce for linear time array questions (bitwise solution) [problem 136]
- Remember you can use XOR (bitwise operators) and with the case of XOR, you can XOr in any order and it will be the same as long as you XOR all the elements. i.e. a XOR b = b XOR a (a XOR b) XOR c == a XOR (b XOR c) returns the same thing. Hence if you had [4, 1, 2, 1, 2], 1 XOR 1 will cancel out to 0, 2 XOR 2 will cancel out to 0 and 4 will be the only number left so we know that that is the number that is different.
- Be careful with Binary Trees: 1) they don't have to be balanced 2) You don't need a while loop to iterate through it if you already are already recursively going through the tree. For this particular question, I only need to check whether the root exists or not: [https://leetcode.com/problems/maximum-depth-of-binary-tree/]
- In a Linked List question, be careful of your loop constraint i.e. while current.next is not None or while current is not None [in reversing a list, we only need to know about the current]
- When asked to delete an entry from a linked list without the head, you CANNOT delete it. You can only copy the values from the next part of the linked list into where it is now (overwrite it)
- Use a lag variable if you have two pointers and need to replace or move something
- Make use of the count function to find how many times something appears
- Remember to use the SET function for questions containing duplicates in an array or similar
- When you have 2 pointers, the base case will usually be when the left crossing the right (recall binary search)
- Use subtraction of ordinal values to find out how far away a character is from a character e.g. to find out how far away you are from A: ord(char) - ord('A) - 1 (instead of creating a dictionary)
- Useful to understand how to use Python Collections (import collections) - collections.Counter literally just builds the dictionary for you
- Use del to delete something from a python dictionary e.g. d = {'a': 1, 'b': 2} --> del['a'] becomes d = {'b': 2}
- Whenever you need to implement an operation without an operator - BIT SHIFTING &, ^ and <<
- Generate all, print all, compute all means BACKTRACKING (https://www.youtube.com/watch?v=Zq4upTEaQyM0)
- Make use of swapping e.g. x1, y1 = x2, y2 in questions that involve coordinates. Also with coordinate questions, if you want to maximise movement, you need to max(abs(x2 - x1), abs(y2 - y1))
- If something says "BALANCE this" and you need two things to equal each other, you can just +1 if its L and -1 if its R (one variable plus and minus it instead of keeping track of two variables) (https://leetcode.com/problems/split-a-string-in-balanced-strings/discuss/403836/C%2B%2BJavaPython-Easy-Solution)
- Much more effective to go through a list with conditions via list comprehensions!!!!
- If it's not a balanced BST, chances are your base case won't be 'if root.left is None and root.right is None'. For unbalanced ones, you usually use 'if root.left' or 'if root.right'
- When you are manipulating something, make sure you save an ORIGINAL COPY OF IT for later if you need it. E.g. when I always do N //=10 and then check whether it works but it doesn't because N is now zero (example q: https://leetcode.com/problems/armstrong-number/submissions/)
- If you have a nested list i.e. [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]], you can iterate through everything using 'for index, score in items'
- Use dictionary.items() to get the items i.e. dict_items([(1, 'a'), (2, 'b'), (3, 'c')])
- In linked lists, it is useful to make a dummy node so we can return this node at the end (points to the head of the list). Also use CUR to always point to the working head of the list (https://leetcode.com/problems/merge-two-sorted-lists/)
- Using enumerate function is very useful when your dictionary indexing gets complicated (https://leetcode.com/problems/two-sum/discuss/17/Here-is-a-Python-solution-in-O(n)-time - see first comment)
- Be careful of intersection of two arrays (whether they want all occurrences of duplicates or not) - you can use pointers if you sort it!
- get() method for dictionary is useful as if you do not normally, if it does not exist in the dictionary, it will error. However, get() will simply return the value. You can default this to a number e.g. get(value, 0) means if the value doesn't exist in the dictionary, it will simply return 0 You can initialise the dictionary really easily this way
nums = [4, 9, 5, 6]
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
print(count)
- When reversing linked list, you want to null the value of your first node
- Always do null pointer checks in linked lists. When detecting cycles, simply use two pointers and make use of the fact that they should never meet
- Reverse String II: Remember you can specify steps in a for loop
- Use ^ to flip bits (XOR operator)
- You can get the right by getting len(row) - left i.e. (832 Flipping An Image)
- Law to find sum of 1, 2, 3, 4, 5.. n -> n * (n-1) / 2
- Linked lists often you have to deal with the even and the odd case
- Finding a missing number in an array - USE XOR
- If you have a problem involvig balanced parentheses, not only can you use a stack, you can also use a count and + or - it
- isDigit() does not work wiht negatives!
- MinStack and MaxStack relies on caching. If you get many items that do not influence the cache, then you can get constant in terms of case. However, you are still bound by linear time.
- Remember you cannot change the number in a tuple!!
- Anything with some kind of words and backspacing or removing letters / comparing them will probably involve a stack
- Learn more about generators (and the yield keyword?)
- set() returns a set class so you cannot just compare it to a list, you must use len() first
- When initialising a dictionary and putting values in, remember this format: It is super useful:
word_dict = {}
for letter in s:
word_dict[letter] = word_dict.get(letter, 0) + 1
Study this way of initialising dictionaries:
def findTheDifference(self, s: str, t: str) -> str:
word_dict = {}
for letter in s:
word_dict[letter] = word_dict.get(letter, 0) + 1
for letter in t:
if word_dict.get(letter, 0) == 0:
return letter
else:
word_dict[letter] -= 1
dic = {}
for ch in s:
dic[ch] = dic.get(ch, 0) + 1
for ch in t:
if dic.get(ch, 0) == 0:
return ch
else:
dic[ch] -= 1
- To check if 2 dictionaries are the same, you can do s1.items() == s2.items()
TREES
- If you need to go through 2 trees, chances are a helper function may help in passing the trees through the arrays
SLIDING WINDOW TIPS
- Things we iterate over sequentially
- Contiguous sequence of elements
- Strings, arrays, linked list
- When you need to calculate something --> minimum, maximum, shortest, contained
Question variants:
- fixed length e.g. max sum subarray of size k
- dynamic variant e.g. smallest sum >= to some value S
- dnymaic variant with auxilary data structure
-
When comparing i with i + 1, you can do it more simpler method of just saving prev and curr variable and updating it
-
Can't use a list in sets!!!! Try to convert it to a tuple first using list comprehension! If you do this, you can then use a set. Can probably do something similar to this if your input is a list of lists:
b_set = (tuple(sorted(x)) for x in combos) b_set = set(b_set) b = [list(x) for x in b_set ] return b
Just want to say that this chapter really helped. The first thing about recursion is DO NOT THINK about all the steps in recursion. This is the Big Recursive Idea.
- Remember to check that you are returning the index and not the actual number, vice versa
- Remember to take care of edge cases where there is 1 or no elements
- Remember to check the case where a certain requirement does not exist (e.g. a question about a sorted array - remmeber to take into account when the array is not sorted)