Cheatsheet

1. [A] 3Sum - Sort list, find complement, use two pointers on rest.
2. [A] Best Time to Buy and Sell Stock - Track prospective new buy prices and max profits along the way.
3. [A] Container With Most Water - Narrow two pointers - shorter one gets narrowed.
4. [A] Contains Duplicate - Keep a set while iterating.
5. [A] Find Minimum in Rotated Sorted Array - Binary search for spot where it's smaller than previous.
6. [A] Maximum Product Subarray - Modified Kadane’s, hold the minimum to handle negatives.
7. [A] Maximum Subarray - Max at i is either value or current best + value.
8. [A] Product of Array Except Self - Product from start, then from end, then multiple w/out.
9. [A] Search in Rotated Sorted Array - Binary search for pivot, then for target.
10. [A] Two Sum - Find the complements, complements-to-index, find the match.
11. [B] Counting Bits - Use DP, bottom-up. Build array, shift by one for previous.
12. [B] Missing Number - XOR the array and the range.
13. [B] Number of 1 Bits - Add n & 1 while shifting down to zero.
14. [B] Reverse Bits - Bit-shift the answer out while shifting the original in.
15. [B] Sum of Two Integers - Just give up if this one comes :(
16. [DP] Climbing Stairs - Basically Fibonacci.
17. [DP] Coin Change - Bottom-up: build up to amount. For each value, iterate denominations and find min.
18. [DP] Combination Sum - DFS where the candidate pool shrinks on every iteration of the sub loop.
19. [DP] Decode Ways - Keep track of previous two as we iterate, recurrence sums it.
20. [DP] House Robber - Recurrence: hr(i) = max(hr(i-1), hr(i-2) + nums[i])
21. [DP] House Robber II - Track with and without start and end, take max.
22. [DP] Jump Game - Keep extending the max as the you loop through.
23. [DP] Longest Common Subsequence - Recurrence: either (i, j) increases the previous or it doesn't and it's one or the other.
24. [DP] Longest Increasing Subsequence - DP: longest at i is max of everything it's larger than that came before.
25. [DP] Unique Paths - DP, recurrence: val(i,j) = val(i - 1,j) + val(i, j - 1)
26. [DP] Word Break - Build a trie using wordDict, iterate string and recurse on new words.
27. [G] Alien Dictionary - Build lex-relevant words, then graph, then topological sort.
28. [G] Clone Graph - Clone all nodes first via BFS, add in associations after.
29. [G] Course Schedule - Build graph while tracking roots. Break down graph while traversing from roots.
30. [G] Graph Valid Tree - Build graph, start at zero, traverse it and expect no cycles, tree has n-1 edges.
31. [G] Longest Consecutive Sequence - Store numbers in a dict along with before and after. BFS after to find the length.
32. [G] Number of Connected Components in an Undirected Graph - Build graph, BFS through to break down the nodes.
33. [G] Number of Islands - BFS-explore all island while mutating grid. Un-mutated afterwards.
34. [G] Pacific Atlantic Water Flow - Reverse flow from each coast, intersect the results.
35. [H] Find Median from Data Stream - Keep two heaps.
36. [H] Top K Frequent Elements - Count and put everything in a heap.
37. [I] Insert Interval - For overlaps, augment the interval's end continuously.
38. [I] Meeting Rooms - Check if overlap.
39. [I] Meeting Rooms II - Use heap to track "current" end times.
40. [I] Merge Intervals - Sort intervals, add them in - if overlap, edit the last one's end.
41. [I] Non-overlapping Intervals - Sort it, remove the one with a longer end.
42. [L] Detect Cycle in a Linked List - Could do the slow/fast thing or just a simple hash.
43. [L] Merge K Sorted Lists - Put all first elements in a heap, for each one that gets popped, add the next one.
44. [L] Merge Two Sorted Lists - Straightforward pointer maintenance.
45. [L] Remove Nth Node From End Of List - Give end a head start of n, go through to find the node, then do pointers.
46. [L] Reorder List - Find the middle using the slow/fast trick, reverse the LL from the middle, merge.
47. [L] Reverse Linked List - Keep previous while iterating.
48. [M] Rotate Image - Figure out the loops - it depends on (n % 2). Manually figure out the rotation.
49. [M] Set Matrix Zeroes - Check if first row/col should be zero, use those to memo zeros, another to set.
50. [M] Spiral Matrix - Keep 4 pointers that narrow on each iteration. Iterate while sane.
51. [M] Word Search - Recursive search through each element, mutate the board to mark visited.
52. [S] Encode and Decode Strings - Use ord to make characters into ascii, chr to bring them back.
53. [S] Group Anagrams - Create dict of 26-tuple to list of strings. Return the values.
54. [S] Longest Palindromic Substring - Test center expansions around 2n + 1 centers, O(n^2) time.
55. [S] Longest Repeating Character Replacement - Sliding window that increases in size when valid. Never contracts.
56. [S] Longest Substring Without Repeating Characters - Iterate through and keep a set of seen-once characters. Keep it up to date.
57. [S] Minimum Window Substring - After count, create window that is a superset. Slide and contract if possible.
58. [S] Palindromic Substrings - Center expansion.
59. [S] Valid Anagram - Compare counts.
60. [S] Valid Palindrome - Python's .isalnum() helps.
61. [S] Valid Parentheses - Use a stack, on open, push close. On close, check match.
62. [T] Add and Search Word - Just a trie.
63. [T] Binary Tree Level Order Traversal - BFS with a side array to push order.
64. [T] Binary Tree Maximum Path Sum - Recursion while tracking connectable and not connectable max.
65. [T] Construct Binary Tree from Preorder and Inorder Traversal - Find sub tree inorder and preorder and build recursively.
66. [T] Implement Trie (Prefix Tree) - Implement a trie.
67. [T] Invert Binary Tree - BFS or DFS while inverting.
68. [T] Kth Smallest Element in a BST - Inorder while passing in remaining values.
69. [T] Lowest Common Ancestor of BST - Find both paths, compare lists, and find ancestor.
70. [T] Maximum Depth of Binary Tree - BFS or DFS while tracking height.
71. [T] Same Tree - Traverse both, DFS or BFS is fine.
72. [T] Serialize and Deserialize Binary Tree - Recursively create a raw version, use JSON after that.
73. [T] Subtree of Another Tree - BFS with nested double BFS. Alternatively, recursion with same tree helper.
74. [T] Validate Binary Search Tree - Check left and right, careful with range.
75. [T] Word Search II - Build trie, try each position. Mutating input can track visited.