1. In general, brute force (compare every single combination) is O(n^2), and then sorting is always better at O(n log n).
2. Linked Lists
2.1. Use a dummy node, and then return dummyNode.next at the very end (merge two sorted linked lists)
2.2. One list might not have ended yet after a while(l1 && l2)
2.3. Tortoise Hare 1) fast/slow 2) set another slow to head and traverse until intersection
3. Problem Solving Approaches/Techniques
3.1. Start with an extremely simple case
3.2. Try to connect the dots behind input and output, even without knowing the algorithm
3.2.1. In other words, given a sufficiently difficult case, how would your BRAIN naturally solve it?
3.3. Pry open from different angles, even visual/geometric ones (in the case of a matrix)
3.3.1. https://leetcode.com/problems/shortest-unsorted-continuous-subarray/Figures/581/Unsorted_subarray_2.PNG
3.4. Case analysis on base cases
3.4.1. E.g. [1,2] vs. [2,1] vs. [2,2] vs. [1,2,3] when examining base cases
3.5. What laws can we impose that we are absolutely sure about?
3.5.1. What are the bounds of what you’re given?
3.5.1.1. If asked to make IP addresses, then you know there can only be 3 periods, and one for loop for each part of the address
3.5.1.2. If dealing with a phone numpad, there can only be 0-9 keys and 3-4 letters for each code. Constantize early!
3.6. Look for an easier pattern in the problem statement itself before spending too long in compromising brute force land
3.7. Convert into another problem
4. Writing the actual code
4.1. Double-check (no shit) PROBLEMATIC SPOTS after: > vs. >=, i++ vs. —, off-by-one
5. Illuminating Problems
5.1. Lowest Common Ancestor
5.2. Shortest unsorted continuous array
5.3. Max diameter of binary tree
5.4. Meeting Rooms I
5.5. Longest repeating substring (by changing no more than `k` characters)
5.5.1. This question really is just asking you to keep track of a sliding window that is within the constraint of Len - (max num of repeating characters) <= k. Making the logical leap is not easy.
5.5.2. This question really is just asking you to keep track of a sliding window that is within the constraint of Len - (max num of repeating characters) <= k. Making the logical leap is not easy.
5.6. Buy and sell stock ONCE
5.6.1. The max must come after the min - the question itself has a constraint (yes, really)
5.6.2. It is not intuitive to me, but since selling price always comes after buying price, it makes sense to keep track of the min price
5.7. Largest number
5.7.1. Why don’t you just compare the concatenation
5.8. Happy Number
5.8.1. Cycle detection doesn’t apply to only linked lists
5.9. Top K Frequent Words
5.9.1. Requires you to know how to only keep top K elements in a heap and not more (same with K Closest points to origin) - hint: keep the ones you don't want at the top of the heap to easily drop them off at O(1) time!
5.10. Longest common subsequence
5.10.1. Using a 2D n*m matrix, 1) you only compare current character 2) you reference left and top to get max(left, top)+(isSame ? 1 : 0)
5.10.2. Do ABC vs. AC first
5.11. Reorder List
5.12. Convert Sorted Array to Binary Search Tree
5.12.1. Set node.left = helper(...), node.right = helper(...), while helper() itself returns a node at the end.
5.13. Regions between slashes
5.13.1. View slashes as rivers and regions as islands...
6. Algorithms
6.1. Dynamic Programming (bottom up approaches really require you to connect the dots between input and output)
6.1.1. It’s always the max() of something
6.1.2. Kadane’s, sliding window is the optimization of DP
6.1.3. Try filling up a table (n*n matrix) and see if you can establish a pattern
6.1.4. Count everything up to the num given (coin change problem) (solving sub problems)
6.1.5. Refer to a previously computed solution (that's the whole point) in some adjacent/diagonal (depends!) matrix cell.
6.2. Binary Search
6.3. Backtracking
6.3.1. DFS
6.3.2. Generate all combinations for phone number keypad
6.4. Cycle detection - can be applied to both linked lists or just about “anything” with a cycle involved, e.g. Happy Number
7. Data Structures
7.1. Heap - top “K”....
7.1.1. Biggest mistake: when sifting down, there are multiple possibilities for where the next children are (at Len-1, at Len-2, at Len-n), and you need to catch each of them
7.2. Matrix
7.2.1. N=2,3,4,5 can vary and break your code
7.2.2. If iterating by layer, don’t forget about offsets
7.2.2.1. In “Rotate Image”, you got screwed because when shifting by a factor of `k`, deducing the coordinates isn’t as simple
7.2.3. Look at it from different angles to establish relationships (top right, bottom left)
7.2.4. Attempt to reduce search space / reduce dimensions
7.3. Arrays
7.3.1. “Numbers are in the range of 0 to N” is a dead give away
7.3.2. Set to negative to mark as “seen”
7.3.2.1. (And remember to use Math.abs)
7.3.3. Sliding Window
7.3.4. Use existing parts of the array by keeping count and then overwriting
7.4. Strings
7.4.1. Abuse the fact that strings usually only contain [a-z] thus you can use a new Array(26)
7.4.2. Sliding Window
7.4.2.1. Sliding window, accompanied with an auxillary data structure (dict{} or char[26]) can be used to solve a lot of DP-ish problems.
7.5. Stacks - used for keep tracking of O( > 1 ) items “in the past” that have some sort of priority to them, e.g. Daily Temperature question where you need to keep track of some past max
7.6. Binary Tree
7.6.1. Binary Search Tree - abuse the BST invariant in your recursive code
7.6.2. Fold Subtrees into ‘#’
7.6.3. The root is not necessarily part of the longest path
7.6.4. Level order traversal using BFS
7.6.4.1. let queue = [root]; while(queue.length) { const size = queue.length; for(let i=0; i<size; i++) { If you do i<queue.length the goalposts will shift
7.7. Graphs
7.7.1. Euclerian
7.7.2. Strategy: build graph, traverse it.
7.7.2.1. BFS and DFS both take O(E+V) time but BFS consumes more memory
7.7.3. Can use matrix or objects - up to you
8. Techniques
8.1. Sliding Window: Prevents extra work being done if you can just process a new element and ditch the tail element ( https://www.educative.io/courses/grokking-the-coding-interview/7D5NNZWQ8Wr)
8.2. Recursion
8.2.1. Set global vs. Return something vs. Throw away returned value
8.2.2. Calling DFS twice at a DFS call results in 2^h calls as you go down the binary tree