Terrible LeetCode in Kotlin:
Another day, another LeetCode question (for now). Today, I'm running through #310 Minimum Height Trees. The problem provides an adjacency list of pairs, and an integer n that indicates that there are nodes 0..n-1 within the graph.
My attempt at a solution was straightforward, but unfortunately too slow. It involved calculating the height of every node as a root, storing the item inside of a priority queue, and then popping all of the minimums out of that priority queue. This runs in approximately O(V^2) time, where V is the number of vertices or nodes within the graph.
I took a peek at the solution after the 50 minutes or so of attempting the problem. The solution uses a "topological sort"-like process where leaf nodes are removed layer by layer, until we get to the nodes which will have equal and minimum height in the middle. This provides a solution to our problem in O(V) time instead.
I work in Kotlin as my LeetCode programming language because my current focus is on Android app development. Kotlin is interoperable with Java, so the solution should be relatively similar albeit with some more boilerplate checks for nulls and such.
Current Grind:
Grind75 list, 22 weeks/7 hours per week, [77/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Problem discussion
05:46 - Coding begins, O(V^2) naive solution
52:48 - Solution discussion, topological sort