Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

class Solution {
    fun fixedPoint(arr: IntArray): Int {
        var left = 0
        var right = arr.size - 1
        var answer = -1
        
        while (left <= right) {
            val mid = (left + right) / 2
            
            if (arr[mid] == mid) {
                answer = mid
                right = mid - 1
            } else if (arr[mid] < mid) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return answer
    }
}

Input: s = "00110"
Output: 1

class Solution {
    fun minFlipsMonoIncr(s: String): Int {
        val n = s.length
        val left = IntArray(n + 1)
        val right = IntArray(n + 1)
        
        for (i in 0 until n) {
            left[i + 1] = left[i] + if (s[i] == '1') 1 else 0
        }
        
        for (i in n - 1 downTo 0) {
            right[i] = right[i + 1] + if (s[i] == '0') 1 else 0
        }
        
        var result = Int.MAX_VALUE
        for (i in 0..n) {
            result = minOf(result, left[i] + right[i])
        }
        return result
    }
}

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

class Solution {
    fun deepestLeavesSum(root: TreeNode?): Int {
        var deepestSum = 0
        var depth = 0
        val stack = ArrayDeque<Pair<TreeNode, Int>>()
        stack.push(Pair(root!!, 0))

        while (stack.isNotEmpty()) {
            val (node, currDepth) = stack.pop()

            if (node.left == null && node.right == null) {
                if (depth < currDepth) {
                    deepestSum = node.`val`
                    depth = currDepth
                } else if (depth == currDepth) {
                    deepestSum += node.`val`
                }
            } else {
                node.right?.let { stack.push(Pair(it, currDepth + 1)) }
                node.left?.let { stack.push(Pair(it, currDepth + 1)) }
            }
        }
        return deepestSum
    }
}

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

class Solution {
    fun minPushBox(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
        
        fun isValid(x: Int, y: Int) = x in 0 until m && y in 0 until n && grid[x][y] != '#'
        
        var player = intArrayOf(0, 0)
        var box = intArrayOf(0, 0)
        var target = intArrayOf(0, 0)
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                when (grid[i][j]) {
                    'S' -> player = intArrayOf(i, j)
                    'B' -> box = intArrayOf(i, j)
                    'T' -> target = intArrayOf(i, j)
                }
            }
        }
        
        val queue = ArrayDeque<IntArray>()
        val visited = mutableSetOf<String>()
        
        queue.addLast(intArrayOf(player[0], player[1], box[0], box[1], 0))
        visited.add("${player[0]},${player[1]},${box[0]},${box[1]}")
        
        while (queue.isNotEmpty()) {
            val (px, py, bx, by, pushes) = queue.removeFirst()
            if (bx == target[0] && by == target[1]) {
                return pushes
            }
            for ((dx, dy) in directions) {
                val npx = px + dx
                val npy = py + dy
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        val nbx = bx + dx
                        val nby = by + dy
                        if (isValid(nbx, nby) && visited.add("$npx,$npy,$nbx,$nby")) {
                            queue.addLast(intArrayOf(npx, npy, nbx, nby, pushes + 1))
                        }
                    } else if (visited.add("$npx,$npy,$bx,$by")) {
                        queue.addLast(intArrayOf(npx, npy, bx, by, pushes))
                    }
                }
            }
        }
        
        return -1
    }
}

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

class TrieNode {
    val children: MutableMap<Char, TrieNode> = HashMap()
    var isWord: Boolean = false
}

class WordDictionary {
    private val root: TrieNode = TrieNode()

    fun addWord(word: String) {
        var node = root
        for (ch in word) {
            node = node.children.computeIfAbsent(ch) { TrieNode() }
        }
        node.isWord = true
    }

    private fun searchInNode(word: String, node: TrieNode): Boolean {
        var node = node
        for (i in word.indices) {
            val ch = word[i]
            if (!node.children.containsKey(ch)) {
                if (ch == '.') {
                    for (child in node.children.values) {
                        if (searchInNode(word.substring(i + 1), child)) {
                            return true
                        }
                    }
                }
                return false
            } else {
                node = node.children[ch]!!
            }
        }
        return node.isWord
    }

    fun search(word: String): Boolean {
        return searchInNode(word, root)
    }
}

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

class Solution {
    fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
        val n = graph.size
        val visited = mutableSetOf<Int>()
        val components = mutableListOf<MutableSet<Int>>()
        
        fun dfs(node: Int) {
            val stack = mutableListOf(node)
            val component = mutableSetOf<Int>()
            while (stack.isNotEmpty()) {
                val u = stack.removeAt(stack.lastIndex)
                if (u !in visited) {
                    visited.add(u)
                    component.add(u)
                    for (v in 0 until n) {
                        if (graph[u][v] == 1 && v !in visited) {
                            stack.add(v)
                        }
                    }
                }
            }
            components.add(component)
        }
        
        for (i in 0 until n) {
            if (i !in visited) {
                dfs(i)
            }
        }
        
        val infectedInComponent = IntArray(components.size)
        val nodeToComponent = IntArray(n) { -1 }
        
        for ((idx, component) in components.withIndex()) {
            for (node in component) {
                nodeToComponent[node] = idx
                if (node in initial) {
                    infectedInComponent[idx]++
                }
            }
        }
        
        var minInfected = Int.MAX_VALUE
        var resultNode = initial.minOrNull()!!
        
        for (node in initial) {
            val componentIdx = nodeToComponent[node]
            if (infectedInComponent[componentIdx] == 1) {
                val componentSize = components[componentIdx].size
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize
                    resultNode = node
                }
            }
        }
        
        return resultNode
    }
}

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

class MovingAverage(size: Int) {
    private val size = size
    private val queue: ArrayDeque<Int> = ArrayDeque()
    private var sum = 0
    
    fun next(`val`: Int): Double {
        queue.addLast(`val`)
        sum += `val`
        if (queue.size > size) {
            sum -= queue.removeFirst()
        }
        return sum.toDouble() / queue.size
    }
}

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)
    }
}