Kotlin | Rust
\n\n\nhttps://youtu.be/BnRaBTepoqI\n\n#### Join me on Telegram\n\nhttps://t.me/leetcode_daily_unstoppable/798\n\n#### Problem TLDR\n\nQueries of max beauty for 
![1.webp](https://assets.leetcode.com/users/images/beb7dc46-abd3-4dd2-bbb9-040673e26d39_1731399874.2511334.webp)\n\n\nhttps://youtu.be/BnRaBTepoqI\n\n#### Join me on Telegram\n\nhttps://t.me/leetcode_daily_unstoppable/798\n\n#### Problem TLDR\n\nQueries of `max` beauty for `q[i]` price #medium #binary_search\n\n#### Intuition\n\nIf we sort everything, we can do a line sweep: for each increasing `query` price move `items` pointer and pick `max` beauty.\n\nMore shorter solution is to do a BinarySearch for each query. But we should precompute `max beauty` for each item price range.\n\n#### Approach\n\n* Kotlin has a `binarySearchBy` but only for `List`\n* Rust & C++ has a more elegant `partition_point`\n\n#### Complexity\n\n- Time complexity:\n$$O(nlog(n))$$ for the Line Sweep and for the Binary Search\n\n- Space complexity:\n$$O(n)$$\n\n#### Code\n\n```kotlin []\n\n    fun maximumBeauty(items: Array<IntArray>, queries: IntArray): IntArray {\n        items.sortWith(compareBy({ it[0] }, { -it[1] }))\n        for (i in 1..<items.size) items[i][1] = max(items[i][1], items[i - 1][1])\n        return IntArray(queries.size) { i ->\n            var j = items.asList().binarySearchBy(queries[i]) { it[0] }\n            if (j == -1) 0 else if (j < 0) items[-j - 2][1] else items[j][1]\n        }\n    }\n\n```\n```rust []\n\n    pub fn maximum_beauty(mut items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {\n        items.sort_unstable();\n        items.dedup_by(|a, b| a[1] <= b[1]);\n        queries.iter().map(|&q| {\n            let j = items.partition_point(|t| q >= t[0]);\n            if j < 1 { 0 } else { items[j - 1][1] }\n        }).collect()\n    }\n\n```\n```c++ []\n\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        sort(begin(items), end(items));\n        for (int i = 1; i < items.size(); ++i) items[i][1] = max(items[i][1], items[i - 1][1]);\n        vector<int> res;\n        for (int q: queries) {\n            auto it = partition_point(begin(items), end(items), \n                [q](const auto& x) { return q >= x[0];});\n            res.push_back(it == begin(items) ? 0 : (*(it - 1))[1]);\n        }\n        return res;\n    }\n\n```
['Binary Search', 'C++', 'Rust', 'Kotlin']