Input: num = 48
Output: 68

fun smallestFactorization(num: Int): Int {
    if (num == 1) return 1
    
    var num = num
    val factors = mutableListOf<Int>()
    
    for (i in 9 downTo 2) {
        while (num % i == 0) {
            factors.add(i)
            num /= i
        }
    }
    
    if (num > 1) return 0
    
    var result: Long = 0
    for (factor in factors.asReversed()) {
        result = result * 10 + factor
        if (result > Int.MAX_VALUE) return 0
    }
    
    return result.toInt()
}

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

class RLEIterator(private val encoding: IntArray) {
    private var index = 0

    fun next(n: Int): Int {
        var n = n
        while (index < encoding.size) {
            if (n > encoding[index]) {
                n -= encoding[index]
                index += 2
            } else {
                encoding[index] -= n
                return encoding[index + 1]
            }
        }
        return -1
    }
}

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

class Solution {
    fun shiftingLetters(s: String, shifts: IntArray): String {
        val sArray = s.toCharArray()
        var totalShifts = shifts.sum() % 26
        
        for (i in sArray.indices) {
            val newCharValue = (sArray[i] - 'a' + totalShifts) % 26
            sArray[i] = ('a' + newCharValue)
            totalShifts = (totalShifts - shifts[i]) % 26
        }
        
        return String(sArray)
    }
}

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

class SnakeGame(width: Int, height: Int, food: Array<IntArray>) {
    private val width = width
    private val height = height
    private val food = food
    private var score = 0
    private val snake = ArrayDeque(listOf(intArrayOf(0, 0)))
    private val snakeSet = mutableSetOf(Pair(0, 0))
    private var foodIndex = 0

    fun move(direction: String): Int {
        val head = snake.first()
        val newHead = head.copyOf()
        when (direction) {
            "U" -> newHead[0] -= 1
            "D" -> newHead[0] += 1
            "L" -> newHead[1] -= 1
            "R" -> newHead[1] += 1
        }

        if (newHead[0] < 0 || newHead[0] >= height || newHead[1] < 0 || newHead[1] >= width) {
            return -1
        }

        val newHeadPair = Pair(newHead[0], newHead[1])
        if (snakeSet.contains(newHeadPair) && newHeadPair != Pair(snake.last()[0], snake.last()[1])) {
            return -1
        }

        if (foodIndex < food.size && newHead[0] == food[foodIndex][0] && newHead[1] == food[foodIndex][1]) {
            foodIndex++
        } else {
            val tail = snake.removeLast()
            snakeSet.remove(Pair(tail[0], tail[1]))
        }

        snake.addFirst(newHead)
        snakeSet.add(newHeadPair)

        return snake.size - 1
    }
}

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

class Solution {
    private var count = 0
    
    fun countArrangement(N: Int): Int {
        val nums = (1..N).toList().toIntArray()
        permute(nums, 0)
        return count
    }
    
    private fun permute(nums: IntArray, l: Int) {
        if (l == nums.size) {
            count++
        }
        for (i in l until nums.size) {
            nums.swap(i, l)
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                permute(nums, l + 1)
            }
            nums.swap(i, l)
        }
    }
    
    private fun IntArray.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

class Solution {
    private val dir = arrayOf(intArrayOf(0, 1), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(-1, 0))

    fun longestIncreasingPath(matrix: Array<IntArray>): Int {
        val m = matrix.size
        if (m == 0) return 0
        val n = matrix[0].size
        val outdegree = Array(m + 2) { IntArray(n + 2) }
        val newMatrix = Array(m + 2) { IntArray(n + 2) }

        for (i in 0 until m) {
            for (j in 0 until n) {
                newMatrix[i + 1][j + 1] = matrix[i][j]
            }
        }

        for (i in 1..m) {
            for (j in 1..n) {
                for (d in dir) {
                    if (newMatrix[i][j] < newMatrix[i + d[0]][j + d[1]]) {
                        outdegree[i][j]++
                    }
                }
            }
        }

        val leaves = mutableListOf<IntArray>()
        for (i in 1..m) {
            for (j in 1..n) {
                if (outdegree[i][j] == 0) leaves.add(intArrayOf(i, j))
            }
        }

        var height = 0
        while (leaves.isNotEmpty()) {
            height++
            val newLeaves = mutableListOf<IntArray>()
            for (node in leaves) {
                for (d in dir) {
                    val x = node[0] + d[0]
                    val y = node[1] + d[1]
                    if (newMatrix[node[0]][node[1]] > newMatrix[x][y]) {
                        outdegree[x][y]--
                        if (outdegree[x][y] == 0) newLeaves.add(intArrayOf(x, y))
                    }
                }
            }
            leaves.clear()
            leaves.addAll(newLeaves)
        }

        return height
    }
}

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

class Solution {
    fun compareVersion(version1: String, version2: String): Int {
        val tokens1 = version1.split('.').map { it.toInt() }
        val tokens2 = version2.split('.').map { it.toInt() }

        for (i in 0 until maxOf(tokens1.size, tokens2.size)) {
            val i1 = if (i < tokens1.size) tokens1[i] else 0
            val i2 = if (i < tokens2.size) tokens2[i] else 0

            if (i1 != i2) {
                return if (i1 > i2) 1 else -1
            }
        }
        return 0
    }
}

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

class Node(var `val`: Int) {
    var children: List<Node?> = listOf()
}

class Solution {
    fun preorder(root: Node?): List<Int> {
        val output = mutableListOf<Int>()
        if (root == null) return output
        val stack = LinkedList<Node>()
        stack.add(root)
        
        while (stack.isNotEmpty()) {
            val node = stack.removeLast()
            output.add(node.`val`)
            for (child in node.children.reversed()) {
                if (child != null) {
                    stack.add(child)
                }
            }
        }
        
        return output
    }
}

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

class TimeMap {
    private val keyTimeMap = mutableMapOf<String, MutableMap<Int, String>>()

    fun set(key: String, value: String, timestamp: Int) {
        if (!keyTimeMap.containsKey(key)) {
            keyTimeMap[key] = mutableMapOf()
        }
        keyTimeMap[key]?.put(timestamp, value)
    }

    fun get(key: String, timestamp: Int): String {
        val times = keyTimeMap[key] ?: return ""
        for (currTime in timestamp downTo 1) {
            if (times.containsKey(currTime)) {
                return times[currTime]!!
            }
        }
        return ""
    }
}

Input: root = [1,null,2,3]
Output: [3,2,1]

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun postorderTraversal(root: TreeNode?): List<Int> {
        if (root == null) {
            return emptyList()
        }

        val stack = mutableListOf(root)
        val output = mutableListOf<Int>()

        while (stack.isNotEmpty()) {
            val node = stack.removeAt(stack.lastIndex)
            output.add(node.`val`)
            node.left?.let { stack.add(it) }
            node.right?.let { stack.add(it) }
        }

        return output.asReversed()
    }
}

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

class Solution {
    fun minWindow(s: String, t: String): String {
        if (t.isEmpty() || s.isEmpty()) return ""

        val dictT = t.groupingBy { it }.eachCount().toMutableMap()
        val required = dictT.size
        var l = 0
        var r = 0
        var formed = 0
        val windowCounts = mutableMapOf<Char, Int>()
        var ans = Triple(Int.MAX_VALUE, 0, 0)

        while (r < s.length) {
            val character = s[r]
            windowCounts[character] = windowCounts.getOrDefault(character, 0) + 1

            if (dictT.containsKey(character) && windowCounts[character] == dictT[character]) {
                formed++
            }

            while (l <= r && formed == required) {
                character = s[l]
                if (r - l + 1 < ans.first) {
                    ans = Triple(r - l + 1, l, r)
                }

                windowCounts[character] = windowCounts.getOrDefault(character, 0) - 1
                if (dictT.containsKey(character) && windowCounts[character]!! < dictT[character]!!) {
                    formed--
                }

                l++
            }

            r++
        }

        return if (ans.first == Int.MAX_VALUE) "" else s.substring(ans.second, ans.third + 1)
    }
}

Input: arr = [0]
Output: 1

fun subarrayBitwiseORs(arr: IntArray): Int {
    val result = mutableSetOf<Int>()
    var current = mutableSetOf<Int>()
    for (num in arr) {
        val next = mutableSetOf(num)
        for (x in current) {
            next.add(x or num)
        }
        current = next
        result.addAll(current)
    }
    return result.size

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

class Solution {
    fun findDiagonalOrder(mat: Array<IntArray>): IntArray {
        if (mat.isEmpty()) return intArrayOf()
        val N = mat.size
        val M = mat[0].size
        val result = mutableListOf<Int>()
        
        for (d in 0 until N + M - 1) {
            val intermediate = mutableListOf<Int>()
            var r = if (d < M) 0 else d - M + 1
            var c = if (d < M) d else M - 1
            
            while (r < N && c >= 0) {
                intermediate.add(mat[r][c])
                r++
                c--
            }
            
            if (d % 2 == 0) {
                result.addAll(intermediate.reversed())
            } else {
                result.addAll(intermediate)
            }
        }
        
        return result.toIntArray()
    }
}

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

class Solution {
    fun findRelativeRanks(score: IntArray): Array<String> {
        val N = score.size
        val maxScore = score.maxOrNull()!!
        val scoreToIndex = IntArray(maxScore + 1)
        
        for (i in score.indices) {
            scoreToIndex[score[i]] = i + 1
        }
        
        val MEDALS = arrayOf("Gold Medal", "Silver Medal", "Bronze Medal")
        val rank = Array(N) { "" }
        var place = 1
        
        for (i in maxScore downTo 0) {
            if (scoreToIndex[i] != 0) {
                val originalIndex = scoreToIndex[i] - 1
                rank[originalIndex] = if (place < 4) MEDALS[place - 1] else place.toString()
                place++
            }
        }
        
        return rank
    }
}

Input: left = "4", right = "1000"
Output: 4

class Solution {
    fun isPalindrome(x: Long): Boolean {
        val s = x.toString()
        return s == s.reversed()
    }

    fun superpalindromesInRange(left: String, right: String): Int {
        val leftNum = left.toLong()
        val rightNum = right.toLong()
        var count = 0

        for (i in 1 until 100000) {
            val s = i.toString()
            val palin1 = (s + s.reversed()).toLong()
            val palin2 = (s + s.dropLast(1).reversed()).toLong()

            if (palin1 * palin1 > rightNum) {
                break
            }
            if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
                count++
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
                count++
            }
        }

        return count
    }
}

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val memo = Array(coins.size) { IntArray(amount + 1) { -1 } }
        
        fun numberOfWays(i: Int, amount: Int): Int {
            if (amount == 0) return 1
            if (i == coins.size) return 0
            if (memo[i][amount] != -1) return memo[i][amount]
            
            memo[i][amount] = if (coins[i] > amount) {
                numberOfWays(i + 1, amount)
            } else {
                numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
            }
            return memo[i][amount]
        }
        
        return numberOfWays(0, amount)
    }
}