310.minimum-height-trees.md

310. Minimum Height Trees

My BFS Attempt (TLE)

fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
    val results = mutableListOf<Int>()
    val heights = IntArray(n)
    val graph = buildGraph(n, edges)
    val minHeap = PriorityQueue<Pair<Int, Int>>() { p1, p2 -> p1.second - p2.second }
    graph.keys.forEach { vertex -> 
        minHeap.add(vertex to bfs(graph, vertex))
    }
    
    val minItem = minHeap.poll()!!
    results.add(minItem.first)
    val minHeight = minItem.second
    while (!minHeap.isEmpty() && minHeap.peek()!!.second == minHeight) {
        results.add(minHeap.poll()!!.first)
    }
    return results
}

private fun buildGraph(n: Int, edges: Array<IntArray>): Map<Int, Set<Int>> {
    val graph = hashMapOf<Int, MutableSet<Int>>()
    for (i in 0 until n) {
        graph.put(i, mutableSetOf())
    }
    edges.forEach { 
        graph[it[0]]?.add(it[1])
        graph[it[1]]?.add(it[0])
    }
    return graph
}

private fun bfs(graph: Map<Int, Set<Int>>, source: Int): Int {
    var height = -1
    val queue = ArrayDeque<Int>()
    val visited = hashSetOf<Int>()
    queue.addLast(source)
    while (!queue.isEmpty()) {
        val size = queue.size
        for (i in 0 until size) {
            val node = queue.removeFirst()
            visited.add(node)
            graph[node]!!.forEach { x -> 
                if (!visited.contains(x)) {
                    queue.addLast(x)
                }
            }
        }
        if (!queue.isEmpty()) height++
    }
    return height
}

Second Attempt (TLE)

import kotlin.math.*

class Solution {
    
    fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
        if (edges.size == 0) return listOf<Int>(0)
        val edgesMap = convert(edges)
        val heights = hashMapOf<Int, Int>()
        for (i in 0 until n) {
            val visited = hashSetOf<Int>()
            val height = getHeights(edgesMap, i, visited)
            heights[i] = height
        }

        val buckets = Array<MutableList<Int>>(n + 1) { _ -> mutableListOf<Int>()}
        for (i in heights.keys) {
            val height = heights[i]!!
            buckets[height].add(i)
        }
        for (i in 0 until buckets.size) {
            if (buckets[i].isNotEmpty()) return buckets[i]
        }
        return mutableListOf<Int>()
    }

    private fun convert(edges: Array<IntArray>): HashMap<Int, HashSet<Int>> {
        val matrix = hashMapOf<Int, HashSet<Int>>()
        for (i in 0 until edges.size) {
            val pair = edges[i]
            if (matrix.containsKey(pair[0])) {
                matrix[pair[0]]!!.add(pair[1])
            } else {
                matrix[pair[0]] = hashSetOf(pair[1])
            }

            if (matrix.containsKey(pair[1])) {
                matrix[pair[1]]!!.add(pair[0])
            } else {
                matrix[pair[1]] = hashSetOf(pair[0])
            }
        }
        return matrix
    }

    private fun getHeights(edges: HashMap<Int, HashSet<Int>>, root: Int, visited: HashSet<Int>): Int {
        if (visited.contains(root)) return 0
        if (edges[root] == null || edges[root]?.isEmpty() == true) return 1
        visited.add(root)
        var heights = Int.MIN_VALUE
        edges[root]?.forEach { child ->
            heights = max(heights, getHeights(edges, child, visited) + 1)
        }
        return heights
    }
}