🔥BEATS 💯 % 🎯 | 2 SOLUTIONS | 2nd one is SIMPLE| ✨SUPER EASY BEGINNERS 👏
\n\n---\n\n### Intuition\nTo find the maximum beauty of an item within a given price, we can use a sorted list of items by price and then determine the highest 
![image.png](https://assets.leetcode.com/users/images/00d9e7f4-7b88-4e1c-a8a6-ad5e981d90a8_1731389730.8411446.png)\n\n---\n\n### Intuition\nTo find the maximum beauty of an item within a given price, we can use a sorted list of items by price and then determine the highest beauty available for each query price.\n\n### Approach\n1. **Sort Items**: Sort items by price in ascending order.\n2. **Filter and Build a Result List**: Build a list where each entry is a unique price with the highest beauty up to that price.\n3. **Query Search**: For each query, use binary search to find the maximum beauty available within the given budget.\n\n### Complexity\n- **Time Complexity**: Sorting items takes \\(O(n \\log n)\\), and answering each query takes \\(O(q \\log n)\\) due to binary search.\n- **Space Complexity**: \\(O(n + q)\\) for storing the results and answers.\n\n---\n\n\n```dart []\nclass Solution {\n  List<int> maximumBeauty(List<List<int>> items, List<int> queries) {\n    items.sort((a, b) => a[0].compareTo(b[0]));\n    List<List<int>> res = [\n      [0, 0, double.maxFinite.toInt()]\n    ];\n\n    for (List<int> item in items) {\n      int price = item[0], beauty = item[1];\n      if (beauty > res.last[1]) {\n        res.last[2] = price;\n        res.add([price, beauty, double.maxFinite.toInt()]);\n      }\n    }\n\n    List<int> ans = List.filled(queries.length, 0);\n    for (int j = 0; j < queries.length; j++) {\n      int x = queries[j];\n      for (int i = res.length - 1; i >= 0; i--) {\n        if (res[i][0] <= x) {\n          ans[j] = res[i][1];\n          break;\n        }\n      }\n    }\n    return ans;\n  }\n}\n```\n\n\n```python []\nfrom bisect import bisect_right\n\nclass Solution:\n    def maximumBeauty(self, items, queries):\n        items.sort()\n        res = [(0, 0)]\n        \n        for price, beauty in items:\n            if beauty > res[-1][1]:\n                res.append((price, beauty))\n        \n        ans = []\n        for x in queries:\n            i = bisect_right(res, (x, float(\'inf\'))) - 1\n            ans.append(res[i][1])\n        \n        return ans\n```\n\n\n```javascript []\nclass Solution {\n  maximumBeauty(items, queries) {\n    items.sort((a, b) => a[0] - b[0]);\n    const res = [[0, 0]];\n    \n    for (const [price, beauty] of items) {\n      if (beauty > res[res.length - 1][1]) {\n        res.push([price, beauty]);\n      }\n    }\n    \n    return queries.map(x => {\n      let i = 0;\n      while (i < res.length && res[i][0] <= x) i++;\n      return res[i - 1][1];\n    });\n  }\n}\n```\n\n\n```java []\nimport java.util.*;\n\nclass Solution {\n  public int[] maximumBeauty(int[][] items, int[] queries) {\n    Arrays.sort(items, (a, b) -> Integer.compare(a[0], b[0]));\n    List<int[]> res = new ArrayList<>();\n    res.add(new int[]{0, 0});\n\n    for (int[] item : items) {\n      int price = item[0], beauty = item[1];\n      if (beauty > res.get(res.size() - 1)[1]) {\n        res.add(new int[]{price, beauty});\n      }\n    }\n\n    int[] ans = new int[queries.length];\n    for (int i = 0; i < queries.length; i++) {\n      int x = queries[i];\n      int idx = Collections.binarySearch(res, new int[]{x + 1, 0},\n                                         Comparator.comparingInt(a -> a[0])) - 1;\n      if (idx < 0) idx = -idx - 2;\n      ans[i] = res.get(idx)[1];\n    }\n    return ans;\n  }\n}\n```\n\n\n```cpp []\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n  vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n    sort(items.begin(), items.end());\n    vector<pair<int, int>> res = {{0, 0}};\n    \n    for (auto &item : items) {\n      int price = item[0], beauty = item[1];\n      if (beauty > res.back().second) {\n        res.push_back({price, beauty});\n      }\n    }\n\n    vector<int> ans;\n    for (int x : queries) {\n      int idx = upper_bound(res.begin(), res.end(), make_pair(x, INT_MAX)) - res.begin() - 1;\n      ans.push_back(res[idx].second);\n    }\n    return ans;\n  }\n};\n```\n\n\n```go []\nimport (\n  "sort"\n)\n\nfunc maximumBeauty(items [][]int, queries []int) []int {\n  sort.Slice(items, func(i, j int) bool {\n    return items[i][0] < items[j][0]\n  })\n  \n  res := [][]int{{0, 0}}\n  for _, item := range items {\n    price, beauty := item[0], item[1]\n    if beauty > res[len(res)-1][1] {\n      res = append(res, []int{price, beauty})\n    }\n  }\n  \n  ans := make([]int, len(queries))\n  for i, x := range queries {\n    idx := sort.Search(len(res), func(j int) bool { return res[j][0] > x }) - 1\n    ans[i] = res[idx][1]\n  }\n  \n  return ans\n}\n```\n\n---\n\n# 2nd Simple Solution\n\nHere\'s the solution in multiple programming languages.\n\n---\n\n### Intuition\nThe task involves finding the maximum beauty of an item within a given price range for each query. Sorting and binary searching for the maximum beauty within budget is a straightforward approach.\n\n### Approach\n1. **Sort Items by Price**: Sort the items by price and then iterate to keep track of the maximum beauty for each price.\n2. **Binary Search for Queries**: Use binary search to find the maximum beauty available for each query price by searching through the sorted list.\n\n### Complexity\n- **Time Complexity**: Sorting the items takes \\(O(n \\log n)\\) time. Each query is processed in \\(O(\\log n)\\) due to binary search, making it \\(O((n + q) \\log n)\\) overall.\n- **Space Complexity**: \\(O(n)\\) for storing the intermediate maximum beauty at each price point.\n\n---\n\n### Code Implementation\n\n```dart []\nclass Solution {\n  List<int> maximumBeauty(List<List<int>> items, List<int> queries) {\n    items.sort((a, b) => a[0].compareTo(b[0]));\n    List<List<int>> sortedBeauty = [];\n    sortedBeauty.add(items.first);\n    int maxBeauty = items.first[1];\n\n    for (int i = 1; i < items.length; i++) {\n      int newPrice = items[i][0];\n      int newBeauty = items[i][1];\n      maxBeauty = max(maxBeauty, newBeauty);\n      if (newPrice != sortedBeauty.last[0]) {\n        sortedBeauty.add([newPrice, maxBeauty]);\n      } else {\n        sortedBeauty.last[1] = maxBeauty;\n      }\n    }\n\n    return queries.map((query) => _getMaxBeauty(sortedBeauty, query)).toList();\n  }\n\n  int _getMaxBeauty(List<List<int>> sortedBeauty, int query) {\n    int res = 0, start = 0, end = sortedBeauty.length - 1;\n    while (start <= end) {\n      int mid = start + (end - start) ~/ 2;\n      if (sortedBeauty[mid][0] <= query) {\n        res = sortedBeauty[mid][1];\n        start = mid + 1;\n      } else {\n        end = mid - 1;\n      }\n    }\n    return res;\n  }\n}\n```\n\n```python []\nfrom bisect import bisect_right\n\nclass Solution:\n    def maximumBeauty(self, items, queries):\n        items.sort()\n        sorted_beauty = [[items[0][0], items[0][1]]]\n        max_beauty = items[0][1]\n\n        for price, beauty in items[1:]:\n            max_beauty = max(max_beauty, beauty)\n            if price != sorted_beauty[-1][0]:\n                sorted_beauty.append([price, max_beauty])\n            else:\n                sorted_beauty[-1][1] = max_beauty\n\n        def get_max_beauty(query):\n            idx = bisect_right(sorted_beauty, [query, float(\'inf\')]) - 1\n            return sorted_beauty[idx][1] if idx >= 0 else 0\n\n        return [get_max_beauty(query) for query in queries]\n```\n\n```javascript []\nclass Solution {\n  maximumBeauty(items, queries) {\n    items.sort((a, b) => a[0] - b[0]);\n    const sortedBeauty = [[items[0][0], items[0][1]]];\n    let maxBeauty = items[0][1];\n\n    for (let i = 1; i < items.length; i++) {\n      const [price, beauty] = items[i];\n      maxBeauty = Math.max(maxBeauty, beauty);\n      if (price !== sortedBeauty[sortedBeauty.length - 1][0]) {\n        sortedBeauty.push([price, maxBeauty]);\n      } else {\n        sortedBeauty[sortedBeauty.length - 1][1] = maxBeauty;\n      }\n    }\n\n    return queries.map(query => this.getMaxBeauty(sortedBeauty, query));\n  }\n\n  getMaxBeauty(sortedBeauty, query) {\n    let res = 0, start = 0, end = sortedBeauty.length - 1;\n    while (start <= end) {\n      const mid = Math.floor((start + end) / 2);\n      if (sortedBeauty[mid][0] <= query) {\n        res = sortedBeauty[mid][1];\n        start = mid + 1;\n      } else {\n        end = mid - 1;\n      }\n    }\n    return res;\n  }\n}\n```\n\n```java []\nimport java.util.*;\n\nclass Solution {\n  public int[] maximumBeauty(int[][] items, int[] queries) {\n    Arrays.sort(items, Comparator.comparingInt(a -> a[0]));\n    List<int[]> sortedBeauty = new ArrayList<>();\n    sortedBeauty.add(new int[] {items[0][0], items[0][1]});\n    int maxBeauty = items[0][1];\n\n    for (int i = 1; i < items.length; i++) {\n      int price = items[i][0];\n      int beauty = items[i][1];\n      maxBeauty = Math.max(maxBeauty, beauty);\n      if (price != sortedBeauty.get(sortedBeauty.size() - 1)[0]) {\n        sortedBeauty.add(new int[] {price, maxBeauty});\n      } else {\n        sortedBeauty.get(sortedBeauty.size() - 1)[1] = maxBeauty;\n      }\n    }\n\n    int[] result = new int[queries.length];\n    for (int i = 0; i < queries.length; i++) {\n      result[i] = getMaxBeauty(sortedBeauty, queries[i]);\n    }\n    return result;\n  }\n\n  private int getMaxBeauty(List<int[]> sortedBeauty, int query) {\n    int start = 0, end = sortedBeauty.size() - 1, res = 0;\n    while (start <= end) {\n      int mid = start + (end - start) / 2;\n      if (sortedBeauty.get(mid)[0] <= query) {\n        res = sortedBeauty.get(mid)[1];\n        start = mid + 1;\n      } else {\n        end = mid - 1;\n      }\n    }\n    return res;\n  }\n}\n```\n\n```cpp []\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n  vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n    sort(items.begin(), items.end());\n    vector<pair<int, int>> sortedBeauty;\n    sortedBeauty.push_back({items[0][0], items[0][1]});\n    int maxBeauty = items[0][1];\n\n    for (int i = 1; i < items.size(); i++) {\n      int price = items[i][0];\n      int beauty = items[i][1];\n      maxBeauty = max(maxBeauty, beauty);\n      if (price != sortedBeauty.back().first) {\n        sortedBeauty.push_back({price, maxBeauty});\n      } else {\n        sortedBeauty.back().second = maxBeauty;\n      }\n    }\n\n    vector<int> result;\n    for (int query : queries) {\n      result.push_back(getMaxBeauty(sortedBeauty, query));\n    }\n    return result;\n  }\n\nprivate:\n  int getMaxBeauty(const vector<pair<int, int>>& sortedBeauty, int query) {\n    int res = 0, start = 0, end = sortedBeauty.size() - 1;\n    while (start <= end) {\n      int mid = start + (end - start) / 2;\n      if (sortedBeauty[mid].first <= query) {\n        res = sortedBeauty[mid].second;\n        start = mid + 1;\n      } else {\n        end = mid - 1;\n      }\n    }\n    return res;\n  }\n};\n```\n\n```go []\nimport (\n  "sort"\n)\n\nfunc maximumBeauty(items [][]int, queries []int) []int {\n  sort.Slice(items, func(i, j int) bool {\n    return items[i][0] < items[j][0]\n  })\n  \n  sortedBeauty := [][]int{{items[0][0], items[0][1]}}\n  maxBeauty := items[0][1]\n\n  for i := 1; i < len(items); i++ {\n    price, beauty := items[i][0], items[i][1]\n    maxBeauty = max(maxBeauty, beauty)\n    if price != sortedBeauty[len(sortedBeauty)-1][0] {\n      sortedBeauty = append(sortedBeauty, []int{price, maxBeauty})\n    } else {\n      sortedBeauty[len(sortedBeauty)-1][1] = maxBeauty\n    }\n  }\n\n  res := make([]int, len(queries))\n  for i, query := range queries {\n    res[i] = getMaxBeauty(sortedBeauty, query)\n  }\n  return res\n}\n\nfunc getMaxBeauty(sortedBeauty [][]int, query int) int {\n  res, start, end := 0, 0, len(sortedBeauty)-1\n  for start <= end {\n    mid := start + (end-start)/2\n    if sortedBeauty[mid][0] <= query {\n      res = sortedBeauty[mid][1]\n      start = mid + 1\n    } else {\n      end = mid - 1\n    }\n  }\n  return res\n}\n\nfunc max(a, b int) int {\n  if a > b {\n    return a\n  }\n  return b\n}\n```\n\n\n\n\n\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Array', 'Binary Search', 'C', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']