Java | using Map and Binary Search | O(QlogN+NlogN) | beats 73%
\nclass Solution {\n\tMap<Integer, Integer> map;\n\tint[] res;\n\tint[] maxTillNow;\n\n\tpublic int[] maximumBeauty(int[][] items, int[] q) {\n\t\tmap = new Has
```\nclass Solution {\n\tMap<Integer, Integer> map;\n\tint[] res;\n\tint[] maxTillNow;\n\n\tpublic int[] maximumBeauty(int[][] items, int[] q) {\n\t\tmap = new HashMap<>();\n\t\tres = new int[q.length];\n\n\t\tint x = 0;\n\t\tfor (int[] a : items)\n\t\t\tmap.put(a[0], Math.max(map.getOrDefault(a[0], 0), a[1]));\n\n\t\tmaxTillNow = new int[map.size()];\n\t\tint[] ar = new int[map.size()];\n\n\t\tfor (Map.Entry<Integer, Integer> e : map.entrySet()) {\n\t\t\tar[x++] = (int) e.getKey();\n\t\t}\n\t\tArrays.sort(ar);\n\n\t\tint max = 0;\n\t\tfor (int i = 0; i < ar.length; i++) {\n\t\t\tmax = Math.max(max, map.get(ar[i]));\n\t\t\tmaxTillNow[i] = max;\n\t\t}\n\n\t\tint i = 0;\n\t\tfor (int val : q)\n\t\t\tres[i++] = find(ar, val, ar.length);\n\t\t\n\t\treturn res;\n\t}\n\n\tint find(int[] ar, int val, int n) {\n\t\tint l = 0, r = n - 1, mid = l + (r - l) / 2;\n\t\tint lastLess = -1;\n\t\twhile (l <= r) {\n\t\t\tmid = l + (r - l) / 2;\n\t\t\tif (ar[mid] == val)\n\t\t\t\treturn maxTillNow[mid];\n\t\t\tif (val > ar[mid]) {\n\t\t\t\tlastLess = mid;\n\t\t\t\tl = mid + 1;\n\t\t\t} else\n\t\t\t\tr = mid - 1;\n\t\t}\n\n\t\treturn lastLess >= 0 ? maxTillNow[lastLess] : 0;\n\t}\n}\n```
['Binary Search']