- August 3
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
- https://leetcode.com/problems/longest-common-prefix/description/
- https://leetcode.com/problems/fraction-addition-and-subtraction/description/
- Regex is great! Didn’t know (?=) before

- https://leetcode.com/problems/pacific-atlantic-water-flow/description/
- Misinterpreted the problem many times..

- https://leetcode.com/problems/largest-divisible-subset/description/
- Bad solution:
- Sort.
- use a map with key = last element in a candidate list and value = list itself.
- Traverse the array. Check the element against each element in the map. If the array element is a multiple of the element – and that it’s the longest list satisfying this – put (array element, list appended with array element) to the map. The only other possibility is that the array element is not a multiple of any key, in which case, put (array element, singleton list of the array element)
- O(n^2) speed, O(n) space.

- Some improvements:
- Looks like others’ basic ideas are all the same. One improvement is rather than tracking the whole list, use an array to track the previous index instead.

- Bad solution:
- Trie practices
- https://www.hackerrank.com/challenges/contacts
- I usually use maps to do Tries, but it will be too slow for one test case here.

- https://www.hackerrank.com/challenges/no-prefix-set

- https://www.hackerrank.com/challenges/contacts

- July 31
- Disjoint Set
- https://www.hackerrank.com/challenges/merging-communities
- First attempt: Naive DisjointSet Implementation, with union by rank – in particular, need to go up the forest to find ancestor every time – O(log n) merge and O(log n) query. TLE for most cases.
- Second attempt: Optimize by caching index to oldest ancestor. Lazy updates. TLE for most cases.
- Third attempt: Go back to attempt 1, but use path compression as well. Used array list to track the visited nodes whose parents have to be updated. TLE for most cases.
- Fourth attempt: Use recursion directly to do path compression. Passed.
- Conclusion: it looks like the main reason I get TLE was that in merging, I didn’t return when the two sets already have same ancestor. The official solution doesn’t do union by rank or path compression at all.

- https://www.hackerrank.com/challenges/components-in-graph
- Strongly suspect that bfs would be fast enough as well, but nonetheless solved by disjoint set.

- https://www.hackerrank.com/challenges/kundu-and-tree
- Fairly straightforward, once you realize that you should think of red edges as non-existent edges, and that you are trying to count the number of unordered triples coming from three distinct connected components (only with the black edges).

- https://www.hackerrank.com/challenges/merging-communities

- Disjoint Set
- July 30
- Basic tree problems
- https://www.hackerrank.com/challenges/self-balancing-tree/problem
- AVL tree insertion – did take me a long time to figure out the whole thing
**Redo tomorrow**: it’s possible to not track ancestors and handle all the changes you need during recursion.

- https://www.hackerrank.com/challenges/median
- Fairly likely that keeping a balanced tree together with number of elements in left/right subtree would be sufficient – O(log n) add/remove/get median.
**Redo tomorrow**: don’t want to look at AVL deletion right now.

- https://www.hackerrank.com/challenges/self-balancing-tree/problem
- Stacks
- https://www.hackerrank.com/challenges/balanced-brackets
- https://www.hackerrank.com/challenges/game-of-two-stacks
- First attempt: recursion, TLE for half the test cases.
- Second attempt: key is to build a list of the “smallest” element you can take from the stack each time. Once you build this list, just keep polling until you hit the maximum allowed total. This can be done by tracking two pointers of the respective arrays. Some WA, some TLE
- Third attempt: no need to build out that list – you can track the total sum so far in the process of updating the two pointers, and return the answer right away when ready.
- Fourth attempt: the above is actually wrong: the greedy way of picking the lowest number at every step is logically wrong… does need recursive ideas, so let’s do memoization. Memoization done by a HashMap<Index Pair, Capacity> TLE for half the test cases.
- Fifth attempt: Same as last idea, do bfs on the indices – add index 1 only when permissible, and if this has been calculated before (tracked by a HashSet), don’t do the calculation again. TLE for half of the test cases.
- Sixth attempt: two pointer passing solution. Passed

- Basic tree problems
- July 29
- Basic tree traversal problems
- https://www.hackerrank.com/challenges/is-binary-search-tree
- The editorial’s idea of restricting range is very nice.

- https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor
- The case for binary search tree is trivial – should look at efficient ways for general trees.

- https://www.hackerrank.com/challenges/square-ten-tree
- Have mathematical ideas on how I can do this, but even for small numbers this feels excessively troublesome.
- Find it hard to write down precisely what I have in mind – but roughly something like
- keep dividing 10^{2^k} until the two numbers are the same.
- Add number of intervals of that range that can lie in [L,R]
- split the remaining interval into left and right piece, and do recursion.

- Obstruction:
- to figure out number of intervals in that range, need to subtract L by 1 then divide by 10^{2^k} – seems troublesome to do so.
- to write down the splitted intervals’ range, would need to initialize a fairly big array.

- After reading editorial:
- Certainly a mistake to not trying to solve [1,R] case first – was surprised at how simple that case is.

- https://www.hackerrank.com/challenges/jenny-subtrees

- https://www.hackerrank.com/challenges/is-binary-search-tree

- Basic tree traversal problems