Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

class Solution {
    private lateinit var ans: IntArray
    private lateinit var count: IntArray
    private lateinit var graph: Array<MutableSet<Int>>
    private var N: Int = 0

    fun sumOfDistancesInTree(N: Int, edges: Array<IntArray>): IntArray {
        this.N = N
        graph = Array(N) { mutableSetOf<Int>() }
        ans = IntArray(N)
        count = IntArray(N) { 1 }

        for (edge in edges) {
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        }

        dfs(0, -1)
        dfs2(0, -1)
        return ans
    }

    private fun dfs(node: Int, parent: Int) {
        for (child in graph[node]) {
            if (child != parent) {
                dfs(child, node)
                count[node] += count[child]
                ans[node] += ans[child] + count[child]
            }
        }
    }

    private fun dfs2(node: Int, parent: Int) {
        for (child in graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child]
                dfs2(child, node)
            }
        }
    }

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

class Solution {
    private val graph = mutableMapOf<Int, MutableList<Int>>()
    private val rank = mutableMapOf<Int, Int?>()
    private val connDict = mutableMapOf<Pair<Int, Int>, Boolean>()
    
    fun criticalConnections(n: Int, connections: List<List<Int>>): List<List<Int>> {
        formGraph(n, connections)
        dfs(0, 0)
        val result = mutableListOf<List<Int>>()
        for (conn in connDict.keys) {
            result.add(listOf(conn.first, conn.second))
        }
        return result
    }
    
    private fun dfs(node: Int, discoveryRank: Int): Int {
        if (rank[node] != null) {
            return rank[node]!!
        }
        
        rank[node] = discoveryRank
        var minRank = discoveryRank + 1
        
        for (neighbor in graph[node]!!) {
            val neighRank = rank[neighbor]
            if (neighRank != null && neighRank == discoveryRank - 1) {
                continue
            }
            
            val recursiveRank = dfs(neighbor, discoveryRank + 1)
            
            if (recursiveRank <= discoveryRank) {
                connDict.remove(Pair(min(node, neighbor), max(node, neighbor)))
            }
            
            minRank = minOf(minRank, recursiveRank)
        }
        
        return minRank
    }
    
    private fun formGraph(n: Int, connections: List<List<Int>>) {
        for (i in 0 until n) {
            graph[i] = mutableListOf()
            rank[i] = null
        }
        
        for (edge in connections) {
            val u = edge[0]
            val v = edge[1]
            graph[u]!!.add(v)
            graph[v]!!.add(u)
            connDict[Pair(min(u, v), max(u, v))] = true
        }
    }
}

Input: n = 12
Output: 21

class Solution {
    private fun swap(s: String, i0: Int, i1: Int): String {
        if (i0 == i1) return s
        val chars = s.toCharArray()
        val temp = chars[i0]
        chars[i0] = chars[i1]
        chars[i1] = temp
        return String(chars)
    }
    
    private val list = mutableListOf<String>()
    
    private fun permute(a: String, l: Int, r: Int) {
        if (l == r) {
            list.add(a)
        } else {
            var a = a
            for (i in l..r) {
                a = swap(a, l, i)
                permute(a, l + 1, r)
                a = swap(a, l, i)
            }
        }
    }
    
    fun nextGreaterElement(n: Int): Int {
        val s = n.toString()
        permute(s, 0, s.length - 1)
        list.sort()
        val index = list.indexOf(s)
        if (index != -1 && index < list.size - 1) {
            val result = list[index + 1].toInt()
            if (result <= Int.MAX_VALUE) return result
        }
        return -1
    }
}

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

class Solution {
    private lateinit var memo: Array<IntArray>
    private lateinit var text1: String
    private lateinit var text2: String

    fun longestCommonSubsequence(text1: String, text2: String): Int {
        this.text1 = text1
        this.text2 = text2
        memo = Array(text1.length + 1) { IntArray(text2.length + 1) { -1 } }
        return memoSolve(0, 0)
    }

    private fun memoSolve(p1: Int, p2: Int): Int {
        if (p1 == text1.length || p2 == text2.length) return 0
        if (memo[p1][p2] != -1) return memo[p1][p2]
        val answer: Int
        if (text1[p1] == text2[p2]) {
            answer = 1 + memoSolve(p1 + 1, p2 + 1)
        } else {
            answer = maxOf(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2))
        }
        memo[p1][p2] = answer
        return answer
    }
}

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

class Solution {
    fun findSpecialInteger(arr: IntArray): Int {
        val counts = mutableMapOf<Int, Int>()
        val target = arr.size / 4
        for (num in arr) {
            counts[num] = counts.getOrDefault(num, 0) + 1
            if (counts[num]!! > target) {
                return num
            }
        }
        return -1
    }
}

Input: s = "egg", t = "add"
Output: true

class Solution {
    fun isIsomorphic(s: String, t: String): Boolean {
        val mappingStoT = mutableMapOf<Char, Char>()
        val mappingTtoS = mutableMapOf<Char, Char>()

        for (i in s.indices) {
            val c1 = s[i]
            val c2 = t[i]

            if (!mappingStoT.containsKey(c1) && !mappingTtoS.containsKey(c2)) {
                mappingStoT[c1] = c2
                mappingTtoS[c2] = c1
            } else if (mappingStoT[c1] != c2 || mappingTtoS[c2] != c1) {
                return false
            }
        }

        return true
    }
}

Input: digits = ["1","3","5","7"], n = 100
Output: 20

class Solution {
    fun atMostNGivenDigitSet(digits: Array<String>, n: Int): Int {
        val s = n.toString()
        val K = s.length
        val dp = IntArray(K + 1)
        dp[K] = 1

        for (i in K - 1 downTo 0) {
            for (d in digits) {
                if (d[0] < s[i]) {
                    dp[i] += Math.pow(digits.size.toDouble(), (K - i - 1).toDouble()).toInt()
                } else if (d[0] == s[i]) {
                    dp[i] += dp[i + 1]
                }
            }
        }

        for (i in 1 until K) {
            dp[0] += Math.pow(digits.size.toDouble(), i.toDouble()).toInt()
        }

        return dp[0]
    }
}

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

class Solution {
    fun longestSubsequence(arr: IntArray, difference: Int): Int {
        val dp = mutableMapOf<Int, Int>()
        var answer = 1
        
        for (a in arr) {
            val beforeA = dp.getOrDefault(a - difference, 0)
            dp[a] = beforeA + 1
            answer = maxOf(answer, dp[a]!!)
        }
        
        return answer
    }
}

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

fun splitListToParts(root: ListNode?, k: Int): Array<ListNode?> {
    var length = 0
    var node = root
    while (node != null) {
        length++
        node = node.next
    }

    val partLength = length / k
    val extraParts = length % k

    val parts = Array<ListNode?>(k) { null }
    node = root
    for (i in 0 until k) {
        val partHead = node
        val partSize = partLength + if (i < extraParts) 1 else 0
        for (j in 0 until partSize - 1) {
            if (node != null) node = node.next
        }
        if (node != null) {
            val nextPart = node.next
            node.next = null
            node = nextPart
        }
        parts[i] = partHead
    }

    return parts
}

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]  

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()
        generate("", n, n, result)
        return result
    }

    private fun generate(current: String, left: Int, right: Int, result: MutableList<String>) {
        if (left == 0 && right == 0) {
            result.add(current)
            return
        }
        if (left > 0) generate(current + "(", left - 1, right, result)
        if (right > left) generate(current + ")", left, right - 1, result)
    }
}

Input: nums = [1], k = 0
Output: 0

class Solution {
    fun smallestRangeII(nums: IntArray, k: Int): Int {
        val nums = nums.sorted()
        val n = nums.size
        var result = nums[n - 1] - nums[0]
        val minVal = nums[0]
        val maxVal = nums[n - 1]

        for (i in 0 until n - 1) {
            val high = maxOf(nums[i] + k, maxVal - k)
            val low = minOf(nums[i + 1] - k, minVal + k)
            result = minOf(result, high - low)
        }

        return result
    }
}

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

class Solution {
    fun longestLine(mat: Array<IntArray>): Int {
        if (mat.isEmpty() || mat[0].isEmpty()) return 0
        
        val m = mat.size
        val n = mat[0].size
        var maxLength = 0
        
        val horizontal = Array(m) { IntArray(n) }
        val vertical = Array(m) { IntArray(n) }
        val diagonal = Array(m) { IntArray(n) }
        val antiDiagonal = Array(m) { IntArray(n) }
        
        for (i in mat.indices) {
            for (j in mat[0].indices) {
                if (mat[i][j] == 1) {
                    horizontal[i][j] = (if (j > 0) horizontal[i][j - 1] else 0) + 1
                    vertical[i][j] = (if (i > 0) vertical[i - 1][j] else 0) + 1
                    diagonal[i][j] = (if (i > 0 && j > 0) diagonal[i - 1][j - 1] else 0) + 1
                    antiDiagonal[i][j] = (if (i > 0 && j < n - 1) antiDiagonal[i - 1][j + 1] else 0) + 1
                    
                    maxLength = maxOf(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
                }
            }
        }
        
        return maxLength
    }
}

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

class Solution {
    fun findLUSlength(a: String, b: String): Int {
        return if (a == b) {
            -1
        } else {
            maxOf(a.length, b.length)
        }
    }
}

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

class Solution {
    fun repeatedSubstringPattern(s: String): Boolean {
        val n = s.length
        for (i in 1..n / 2) {
            if (n % i == 0) {
                val pattern = s.substring(0, i).repeat(n / i)
                if (s == pattern) {
                    return true
                }
            }
        }
        return false
    }
}