TC

Get Started. It's Free
TC by

3. Problem Solving Approaches/Techniques

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!

5. Illuminating Problems

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.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.3. Backtracking

6.3.1. DFS

6.3.2. Generate all combinations for phone number keypad

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