Time: 46 ms (53.62%), Space: 81.4 MB (37.28%) - LeetHub

py3-coder · py3-coder · commit 1c3aa1b2ca15 · 2024-11-12T11:09:42.000+05:30
diff --git a/2070-most-beautiful-item-for-each-query/2070-most-beautiful-item-for-each-query.java b/2070-most-beautiful-item-for-each-query/2070-most-beautiful-item-for-each-query.java
@@ -0,0 +1,34 @@
+class Solution {
+    public int[] maximumBeauty(int[][] items, int[] queries) {
+        
+        // Idea  -- Sort the array based on 1st indx .
+        // Binary Search the array 
+        
+        int n = items.length;
+        Arrays.sort(items,(a,b)->(a[0]==b[0])?(b[1]-a[1]):(a[0]-b[0]));
+        
+        int maxi = Integer.MIN_VALUE;
+        for(int i=1;i<n;i++){
+           items[i][1]  = Math.max(items[i-1][1] , items[i][1]);
+           
+        }
+     
+        int[] res =new int[queries.length];
+        for(int i=0;i<queries.length;i++){
+            int start = 0;
+            int end = n-1;
+            while(start<=end){
+                int mid = start+(end-start)/2;
+                if(items[mid][0]<=queries[i]){
+                    start =  mid+1 ;
+                    res[i] = Math.max(res[i] , items[mid][1]);
+                }else{
+                    end = mid-1;
+                }
+            }
+            
+        }
+        return res;
+            
+    }
+}
