LeetCode/kt/most-beautiful-item-for-each-query.kt

class Solution {
    private data class Item(val price: Int, val beauty: Int)

    fun maximumBeauty(
        items: Array<IntArray>,
        queries: IntArray,
    ): IntArray {
        // Sort items by the price
        val items = items.map { Item(it[0], it[1]) }.toMutableList()
        items.sortBy { it.price }
        val maxBeautyTillNow =
            items.scan(0) { runningMax, it ->
                listOf(runningMax, it.beauty).max()
            }

        // Sort queries by the price
        val sortedQueries = queries.withIndex().toMutableList()
        sortedQueries.sortBy { it.value }

        var i = 0
        return sortedQueries.map { query ->
            while (i < items.size && items[i].price <= query.value) {
                i += 1
            }

            IndexedValue(query.index, maxBeautyTillNow[i])
        }.sortedBy { query ->
            query.index
        }.map { query ->
            query.value
        }.toIntArray()
    }
}