TreeMap
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nTreeMap: key - right border, value - pair(width, full height)\n# Complexi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTreeMap: key - right border, value - pair(width, full height)\n# Complexity\n![image.png](https://assets.leetcode.com/users/images/d2462a6e-8eab-423a-8e77-cfd8d48ab506_1727097539.4853752.png)\n# Code\n```kotlin []\nclass Solution {\n    fun fallingSquares(positions: Array<IntArray>): List<Int> {\n        val tree = TreeMap<Int, Pair<Int,Int>>() // key - right border, value - pair(width, full height)\n        var rez : MutableList<Int> = mutableListOf()\n        var max_height = 0\n        for ((left,sideLength) in positions) {\n            val sub = tree.tailMap(left+1) \n            // i find cubes that fell earlier \n            // with a right boundary greater \n            // than the left boundary of the falling one.\n            var tek_max_height = 0\n            for ((pos,pair) in sub) {\n                if (pos-pair.first<left+sideLength) \n                // I check that the previously dropped cube \n                // has a left boundary BEFORE \n                // the right boundary of the current cube.\n                tek_max_height = maxOf(tek_max_height,pair.second)\n            }\n            tree[left+sideLength] = Pair(sideLength,tek_max_height+sideLength)\n            max_height = maxOf(max_height,tek_max_height+sideLength)\n            rez.add(max_height)\n        }\n        return rez\n    }\n}\n```
['Kotlin']